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$$$。