当前没有测试数据。

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 \le k \le n$），请你统计恰好删除 $k$ 个元素后，数组 $a$ 的 $\mathrm{MEX}$ 可能的取值数量。

输入格式

第一行输入一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 数组 $a$ 的长度。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0 \le a_i \le n$）—— 数组的元素。

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

输出格式

对于每个测试用例，输出一行 $n+1$ 个整数 —— 分别对应 $k=0,1,\dots,n$ 时，恰好删除 $k$ 个元素后数组 $\mathrm{MEX}$ 的可能取值数量。

样例输入

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$，得到数组 $[1,0,1,2]$，其 $\mathrm{MEX}$ 为 $3$。
• 若删除唯一的 $2$，得到数组 $[1,0,0,1]$，其 $\mathrm{MEX}$ 为 $2$。

可以证明，这是恰好删除 $1$ 个元素后所有可能的 $\mathrm{MEX}$ 取值。因此 $k=1$ 对应的输出值为 $2$。