← 返回题目列表

Codeforces · 1619/E

E. MEX 和增量

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

Dmitry 有一个 $$$n$$$ 非负整数数组 $$$a_1, a_2, \dots, a_n$$$。

在一次操作中,Dmitry 可以选择任意索引 $$$j$$$ ($$$1 \le j \le n$$$) 并将元素 $$$a_j$$$ 的值增加 $$$1$$$。他可以多次选择相同的索引$$$j$$$。

对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$i$$$,确定 Dmitry 是否可以使数组的 $$$\mathrm{MEX}$$$ 恰好等于 $$$i$$$。如果可能,则确定完成该操作的最少操作数。

数组的 $$$\mathrm{MEX}$$$ 等于数组中不存在的最小非负整数。例如,数组 $$$[3, 1, 0]$$$ 的 $$$\mathrm{MEX}$$$ 等于 $$$2$$$,数组 $$$[3, 3, 1, 4]$$$ 等于 $$$0$$$。

输入

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

测试用例的描述如下。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例描述的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。

保证测试中所有测试用例的值 $$$n$$$ 之和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,输出 $$$n + 1$$$ 整数 - $$$i$$$ 个数字等于可以使数组 $$$\mathrm{MEX}$$$ 等于 $$$i$$$ ($$$0 \le i \le n$$$) 的最小运算次数,如果无法完成,则为 -1。

示例

输入 #1

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

输出 #1

1 1 0 -1 
1 1 2 2 1 0 2 6 
3 0 1 4 3 
1 0 -1 -1 -1 -1 -1 -1 
2 1 0 2 -1 -1

注意

在第一组示例输入中,$$$n=3$$$:

- 要得到$$$\mathrm{MEX}=0$$$,执行一次增量就足够了:$$$a_1$$$++;
- 要得到$$$\mathrm{MEX}=1$$$,执行一次增量就足够了:$$$a_2$$$++;
- 对于给定数组$$$\mathrm{MEX}=2$$$,因此不需要执行增量;
- 通过执行增量不可能得到 $$$\mathrm{MEX}=3$$$。