A - Tallying the Popularity Vote Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は学校の文化祭実行委員として、クラス対抗人気投票の集計を担当しています。この投票にはクラス 1 からクラス N までの N クラスがエントリーしています。また、生徒の人数もちょうど N 人であり、各生徒はいずれか 1 つのクラスに 1 票を投じるか、棄権する（どのクラスにも投票しない）かのいずれかを行いました。

具体的には、生徒 i（1 \leq i \leq N）の投票先は整数 A_i で表されます。A_i = 0 の場合、生徒 i は棄権したことを意味します。A_i \geq 1 の場合、生徒 i はクラス A_i に 1 票を投じたことを意味します。

高橋君は、投票結果を集計し、以下で定義する条件を満たすクラスを「優勝候補」として発表したいと考えています。

優勝候補の定義： クラス x（1 \leq x \leq N）が優勝候補であるとは、クラス x の得票数（クラス x に投票した生徒の人数）が、棄権した生徒の総数（A_i = 0 である生徒 i の人数）より真に多いことを指します。

優勝候補となるクラスの数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq N
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、生徒の人数およびクラスの数を表す整数 N が与えられる。
  • 2 行目には、各生徒の投票先を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • A_i = 0 の場合、生徒 i は棄権したことを意味する。
  • A_i \geq 1 の場合、生徒 i はクラス A_i に投票したことを意味する。

出力

優勝候補となるクラスの数を 1 行で出力せよ。

入力例 1

7
1 2 1 0 1 2 0

出力例 1

1

入力例 2

5
0 0 0 0 0

出力例 2

0

入力例 3

15
3 1 2 3 0 3 1 2 3 0 3 1 4 4 4

出力例 3

3

Score : 266 pts

Problem Statement

Takahashi is in charge of tallying the results of an inter-class popularity vote as a member of his school's cultural festival committee. Classes 1 through N (a total of N classes) are entered in this vote. There are also exactly N students, and each student either cast 1 vote for exactly one class or abstained (voted for no class).

Specifically, the vote of student i (1 \leq i \leq N) is represented by an integer A_i. If A_i = 0, it means student i abstained. If A_i \geq 1, it means student i cast 1 vote for class A_i.

Takahashi wants to tally the voting results and announce the classes that satisfy the following condition as "winning candidates."

Definition of winning candidate: Class x (1 \leq x \leq N) is a winning candidate if and only if the number of votes for class x (the number of students who voted for class x) is strictly greater than the total number of abstaining students (the number of students i with A_i = 0).

Find the number of classes that are winning candidates.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq N
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of students and the number of classes.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing each student's vote.
  • If A_i = 0, it means student i abstained.
  • If A_i \geq 1, it means student i voted for class A_i.

Output

Print the number of classes that are winning candidates in one line.

Sample Input 1

7
1 2 1 0 1 2 0

Sample Output 1

1

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Sample Input 3

15
3 1 2 3 0 3 1 2 3 0 3 1 4 4 4

Sample Output 3

3