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

У Дмитрия есть массив из $$$n$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_n$$$.

За одну операцию он может выбрать произвольный индекс $$$j$$$ ($$$1 \le j \le n$$$) и увеличить значение элемента $$$a_j$$$ на $$$1$$$. Он может выбирать один и тот же индекс $$$j$$$ многократно.

Для каждого $$$i$$$ от $$$0$$$ до $$$n$$$ определите, сможет ли Дмитрий сделать $$$\mathrm{MEX}$$$ массива равным ровно $$$i$$$. Если сможет, то определите, за какое минимальное количество операций.

$$$\mathrm{MEX}$$$ массива равен минимальному целому неотрицательному числу, которого нет в массиве. Например, $$$\mathrm{MEX}$$$ массива $$$[3, 1, 0]$$$ равен $$$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, если этого сделать нельзя.

Пример
Входные данные
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 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$$$, выполняя инкременты, невозможно.