Problem 2. Making Mexes

USACO 2025 February Contest, Bronze

给定一个包含 $N$ 个非负整数的数组 $a$，$a_1, a_2, \dots, a_N$（$1\le N\le 2\cdot 10^5$，$0\le a_i\le N$）。在一次操作中，你可以将 $a$ 的任一元素修改为任意非负整数。

一个数组的

mex

是它不包含的最小非负整数。对于范围 $0$ 到 $N$ 内的每一个 $i$，计算使 $a$ 的 mex 等于 $i$ 所需要的最小操作次数。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

以下一行包含 $a_1,a_2,\dots, a_N$。

输出格式（输出至终端 / 标准输出）：

对于范围 $0$ 到 $N$ 内的每一个 $i$ 输出一行，包含对于 $i$ 的最小操作次数。注意，$a$ 的 mex 对于范围 $0$ 到 $N$ 内的任意 $i$ 值都是可以通过修改取到的。

输入样例：

4
2 2 2 0

输出样例：

1
0
3
1
2

• 为使 $a$ 的 mex 等于 $0$，我们可以将 $a_4$ 修改为 $3$（或任何正整数）。在得到的数组 $[2, 2, 2, 3]$ 中，$0$ 是数组不包含的最小非负整数，因此 $0$ 是数组的 mex。
• 为使 $a$ 的 mex 等于 $1$，我们不需要进行任何修改，因为 $1$ 已经是 $a = [2, 2, 2, 0]$ 中不包含的最小非负整数。
• 为使 $a$ 的 mex 等于 $2$，我们需要修改 $a$ 的前三个元素。例如，我们可以将 $a$ 修改为 $[3, 1, 1, 0]$。

测试点性质： 测试点 2-6：$N\le 10^3$。测试点 7-11：没有额外限制。

供题：Benjamin Qi