G. МЕХанизация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим $$$f(S)$$$. Пусть у вас есть мультимножество (то есть в нём могут быть повторяющиеся элементы) целых неотрицательных чисел $$$S$$$. За одну операцию вы можете выбрать любое непустое подмножество множества $$$S$$$ (в нём также могут быть повторяющиеся элементы), удалить это подмножество (все входящие в него элементы) из множества $$$S$$$, и добавить в $$$S$$$ MEX удалённого подмножества. Вы можете сделать произвольное число таких операций. После всех операций в $$$S$$$ должно остаться ровно $$$1$$$ число. $$$f(S)$$$ — это наибольшее число, которое могло остаться в $$$S$$$ после любого набора операций.

Вам дан массив целых неотрицательных чисел $$$a$$$ длины $$$n$$$. Для каждого из его $$$n$$$ префиксов посчитайте $$$f(S)$$$, если $$$S$$$ — это этот префикс (для $$$i$$$-го префикса $$$S$$$ это первые $$$i$$$ элементов массива $$$a$$$).

MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:

  • MEX массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
  • MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
  • MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ — нет.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — размер массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2 \cdot 10^5$$$) — массив $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите $$$n$$$ чисел: $$$f(S)$$$ для каждого из $$$n$$$ префиксов массива $$$a$$$.

Пример
Входные данные
4
8
179 57 2 0 2 3 2 3
1
0
3
1 0 3
8
1 0 1 2 4 3 0 2
Выходные данные
179 2 3 3 3 4 4 5 
1 
1 2 2 
1 2 2 3 3 5 5 5
Примечание

Рассмотрим первой набор входных данных. Для префикса длины $$$1$$$ изначально мультимножество это $$$\{179\}$$$, если ничего не делать, мы получим $$$179$$$.

Для префикса длины $$$2$$$ изначально мультимножество это $$$\{57, 179\}$$$, и используя данную последовательность операций можно получить $$$2$$$:

  1. применить операцию к $$$\{57\}$$$, мультимножество после этого — $$$\{0, 179\}$$$.
  2. применить операцию к $$$\{179\}$$$, мультимножество после этого — $$$\{0, 0\}$$$.
  3. применить операцию к $$$\{0\}$$$, мультимножество после этого — $$$\{0, 1\}$$$.
  4. применить операцию к $$$\{0, 1\}$$$, мультимножество после этого — $$$\{2\}$$$, это и есть наш ответ.

Рассмотрим второй набор входных данных. Для префикса длины $$$1$$$ изначально мультимножество это $$$\{0\}$$$, если применить к $$$\{0\}$$$ операцию, мы получим мультимножество $$$\{1\}$$$, это и будет ответом.