You are given a sequence of positive integers of length N, a = (a1, a2, ..., aN). 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 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.
Input is given from Standard Input in the following format:
N a1 a2 ... aN
Print the minimum number of elements that needs to be removed so that a will be a good sequence.
4 3 3 3 3
1
We can, for example, remove one occurrence of 3. Then, (3, 3, 3) is a good sequence.
5 2 4 1 4 2
2
We can, for example, remove two occurrences of 4. Then, (2, 1, 2) is a good sequence.
6 1 2 2 3 3 3
0
1 1000000000
1
Remove one occurrence of 109. Then, () is a good sequence.
8 2 7 1 8 2 8 1 8
5
Subtask | Score |
---|---|
1 | 100 |
2 | 0 |