Mock CCC '19 Contest 1 J3 - Liwi Sequence

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

liwi likes a specific type of sequence. He likes an array A with length N if it meets the following conditions:

  • For each element x in A, x must occur exactly x times.

You are given an array V with length N. liwi wants you to remove the minimum number of elements such that the result is a sequence liwi likes.

For example, (4, 4, 4, 4), (), (3, 1, 3, 3) are all valid sequences liwi likes.

Constraints

  • 1 \le N \le 10^5
  • 1 \le A_i \le 10^9, A_i is a positive integer

For 20% of the points, 1 \le N \le 100, and 1 \le A_i \le 100.

Input Specification

The first line will contain a single integer, N.

The next line of input will contain N space separated integers, A_i, such that A_1, A_2, \dots, A_N.

Output Specification

You are to output a single integer - the minimum number of elements that need to be removed such that the array A becomes a sequence liwi likes.

Sample Input 1

5
1 2 2 3 1

Sample Output 1

2

Comments

There are no comments at the moment.