← 返回题目列表

Codeforces · 2123/E

E. MEX 计数

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

将数组的 $$$\mathrm{MEX}$$$ (最小排除值)定义为数组中不存在的最小非负整数。例如,

  • $$$\mathrm{MEX}([2, 2, 1]) = 0$$$ 因为 $$$0$$$ 不在数组中。
  • $$$\mathrm{MEX}([3, 1, 0, 1]) = 2$$$ 因为 $$$0$$$ 和 $$$1$$$ 在数组中,但 $$$2$$$ 不在数组中。
  • $$$\mathrm{MEX}([0, 3, 1, 2]) = 4$$$ 因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 位于数组中,但 $$$4$$$ 不在数组中。

给你一个大小为 $$$n$$$ 的非负整数数组 $$$a$$$。

对于所有 $$$k$$$ ($$$0\leq k \leq n$$$),在从 $$$a$$$ 中精确删除 $$$k$$$ 值后,计算 $$$\mathrm{MEX}(a)$$$ 的可能值的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1,a_2,\dots,a_n$$$ ($$$0\leq a_i\leq n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出一行包含 $$$n+1$$$ 整数 - 删除 $$$k$$$ 值后 $$$\mathrm{MEX}(a)$$$ 的可能值的数量,对于 $$$k=0,1,\dots,n$$$。

示例

输入
复制

5
5
1 0 0 1 2
6
3 2 0 4 5 1
6
1 2 0 1 3 2
4
0 3 4 1
5
0 0 0 0 0

输出
复制

1 2 4 3 2 1
1 6 5 4 3 2 1
1 3 5 4 3 2 1
1 3 3 2 1
1 1 1 1 1 1

注意

在第一个示例中,考虑 $$$k=1$$$。如果删除 $$$0$$$,则会得到以下数组:

1012
所以我们得到$$$\mathrm{MEX}(a) = 3$$$。或者,如果删除 $$$2$$$,则会得到以下数组:
1001
所以我们得到$$$\mathrm{MEX}(a) = 2$$$。可以证明,在删除一个值后,这些是 $$$\mathrm{MEX}(a)$$$ 的唯一可能值。因此 $$$k=1$$$ 的输出是 $$$2$$$。