E. Подсчет MEX
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определите $$$\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$$$ отсутствует.

Вам дан массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел.

Для всех $$$k$$$ ($$$0\leq k \leq n$$$) подсчитайте количество возможных значений $$$\mathrm{MEX}(a)$$$ после удаления ровно $$$k$$$ элементов из $$$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$$$ целых чисел — количество возможных значений $$$\mathrm{MEX}(a)$$$ после удаления ровно $$$k$$$ значений, для $$$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$$$.