The elections (voting)

In the elections for the selection of municipal authorities, there are M mayoral candidates, numbered from 1 to M. In your city, there are N voters, each of whom votes for exactly one of the mayoral candidates. To win the election, a candidate must gather (strictly) more votes than any other candidate.

By noon on election day, K out of N voters have cast their votes. The electoral committee is eager to learn the results and, entirely informally for a secret ballot election, unseals the ballot box and opens the K ballots inside.

Based on the first K votes observed by the electoral committee, help them calculate how many of the mayoral candidates can win the election, after the completion of the electoral process.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the number of voters, candidates, those who voted, and the content of the votes submitted up to the moment of unsealing. Your program should print the number of candidates who have the potential to win the election.

Input Files:

The input files with the name voting.in are text files with the following structure: On the first line there are three integer numbers separated in pairs by a space: the number of voters N, the number of candidates M, the number of those who casted a vote K. On the second line there are K integers separated in pairs by a space : the numbers of the candidates that each of the first K voters voted.

Output Files:

The output files with the name voting.out are text files with the following structure. They consist of exactly one line containing exactly one integer: the number of mayoral candidates who can win the election.

Constraints:

• 1 ~\le~ K ~\le~ N ~\le~ 1.000.000
• 1 ~\le~ M ~\le~ 1.000

Examples of Input - Output files :

1o

STDIN (voting.in)

10 3 7
1 2 2 1 1 3 1

STDOUT (voting.out)

 2

2o

STDIN (voting.in)

 8 2 8
 1 2 1 2 2 1 1 2

STDOUT (voting.out)

0

Explanation of examples:

In the first example, there are three mayoral candidates and ten voters, out of which seven have voted. At the moment, the first mayoral candidate has gathered 4 votes, the second 2, and the third 1. Only the first and second candidates can win the election.

In the second example, there are two mayoral candidates and eight voters, all of whom have voted. The two candidates have an equal number of votes, so neither of them can win the election.

Subproblems:

• For test cases with a total value of 20%, N will be equal to K, meaning all candidates will have voted.
• For test cases with a total value of 30%, M will be equal to 2, meaning there will be only two candidates.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: voting *)

for PASCAL coders

/* USER: username
LANG: C
TASK: voting */

for C coders

/* USER: username
LANG: C++
TASK: voting */

for C++ coders

/* USER: username
LANG: Java
TASK: voting */

for Java coders

# USER: username
# LANG: Python
# TASK: voting

for Python coders