C - Good Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

長さ N の正整数の列 a = (a_1, a_2, ..., a_N) が与えられます。 あなたの目標は、a のうちいくつかの要素を取り除き、a を 良い数列 にすることです。

ここで、数列 b が 良い数列 であるとは、次の条件が成り立つことです。

  • b の各要素 x について、b に値 x はちょうど x 個含まれる。

例えば、(3, 3, 3), (4, 2, 4, 1, 4, 2, 4), () (空の数列) は良い数列です。 一方、(3, 3, 3, 3), (2, 4, 1, 4, 2) は良い数列ではありません。

a を良い数列にするために取り除くべき要素の個数の最小値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • a_i は整数である。
  • 1 \leq a_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N

出力

a を良い数列にするために取り除くべき要素の個数の最小値を出力せよ。

入力例 1

4
3 3 3 3

出力例 1

1

例えば、要素 3 を 1 個取り除くと、(3, 3, 3) は良い数列になります。

入力例 2

5
2 4 1 4 2

出力例 2

2

例えば、要素 4 を 2 個取り除くと、(2, 1, 2) は良い数列になります。

入力例 3

6
1 2 2 3 3 3

出力例 3

0

入力例 4

1
1000000000

出力例 4

1

要素 10^9 を 1 個取り除くと、() は良い数列になります。

入力例 5

8
2 7 1 8 2 8 1 8

出力例 5

5

Score : 300 points

Problem Statement

You are given a sequence of positive integers of length N, a = (a_1, a_2, ..., a_N). Your objective is to remove some of the elements in a so that a will be a good sequence.

Here, an sequence b is a good sequence when the following condition holds true:

  • For each element x in b, the value x occurs exactly x times in b.

For example, (3, 3, 3), (4, 2, 4, 1, 4, 2, 4) and () (an empty sequence) are good sequences, while (3, 3, 3, 3) and (2, 4, 1, 4, 2) are not.

Find the minimum number of elements that needs to be removed so that a will be a good sequence.

Constraints

  • 1 \leq N \leq 10^5
  • a_i is an integer.
  • 1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the minimum number of elements that needs to be removed so that a will be a good sequence.

Sample Input 1

4
3 3 3 3

Sample Output 1

1

We can, for example, remove one occurrence of 3. Then, (3, 3, 3) is a good sequence.

Sample Input 2

5
2 4 1 4 2

Sample Output 2

2

We can, for example, remove two occurrences of 4. Then, (2, 1, 2) is a good sequence.

Sample Input 3

6
1 2 2 3 3 3

Sample Output 3

0

Sample Input 4

1
1000000000

Sample Output 4

1

Remove one occurrence of 10^9. Then, () is a good sequence.

Sample Input 5

8
2 7 1 8 2 8 1 8

Sample Output 5

5