#P11837. [USACO25FEB] Making Mexes B

[USACO25FEB] Making Mexes B

题目描述

给定一个包含 NN 个非负整数的数组 aaa1,a2,,aNa_1, a_2, \dots, a_N1N21051\le N\le 2\cdot 10^50aiN0\le a_i\le N)。在一次操作中,你可以将 aa 的任一元素修改为任意非负整数。

一个数组的 mex 是它不包含的最小非负整数。对于范围 00NN 内的每一个 ii,计算使 aa 的 mex 等于 ii 所需要的最小操作次数。

输入格式

输入的第一行包含 NN

以下一行包含 a1,a2,,aNa_1,a_2,\dots, a_N

输出格式

对于范围 00NN 内的每一个 ii 输出一行,包含对于 ii 的最小操作次数。注意,aa 的 mex 对于范围 00NN 内的任意 ii 值都是可以通过修改取到的。

4
2 2 2 0
1
0
3
1
2

提示

样例 1 解释:

  • 为使 aa 的 mex 等于 00,我们可以将 a4a_4 修改为 33(或任何正整数)。在得到的数组 [2,2,2,3][2, 2, 2, 3] 中,00 是数组不包含的最小非负整数,因此 00 是数组的 mex。

  • 为使 aa 的 mex 等于 11,我们不需要进行任何修改,因为 11 已经是 a=[2,2,2,0]a = [2, 2, 2, 0] 中不包含的最小非负整数。

  • 为使 aa 的 mex 等于 22,我们需要修改 aa 的前三个元素。例如,我们可以将 aa 修改为 [3,1,1,0][3, 1, 1, 0]

  • 测试点 262\sim 6N103N\le 10^3

  • 测试点 7117\sim 11:没有额外限制。