← 返回题目列表

AtCoder · arc087_a

C. 好的序列

中文机器翻译题面 查看原题

分数: 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