分数: 300 点
问题陈述
给定一个长度为正整数的序列 N, a = (a_1, a_2, ..., a_N)。 您的目标是删除其中的一些元素 a 这样 a 将是 好的序列.
这里,一个序列 b 是 好的序列 当以下条件成立时:
- 对于每个元素 x in b,值 x 恰好发生 x 次 b.
例如, (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。然后, (3, 3, 3) 是一个很好的序列。
示例输入 2
5 2 4 1 4 2
示例输出 2
2
例如,我们可以删除两次出现的 4。然后, (2, 1, 2) 是一个很好的序列。
示例输入 3
6 1 2 2 3 3 3
示例输出 3
0
示例输入 4
1 1000000000
示例输出 4
1
删除 1 个出现的 10^9。然后, () 是一个很好的序列。
示例输入 5
8 2 7 1 8 2 8 1 8
示例输出 5
5