D. Задача посложнее
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность положительных целых чисел. Положительное целое число называется модой последовательности, если оно встречается максимальное количество раз среди всех положительных целых чисел. Например, модой последовательности $$$[2,2,3]$$$ является $$$2$$$, а для последовательности $$$[9,9,8,8,7,7]$$$ может считаться модой любое из чисел $$$9$$$, $$$8$$$ или $$$7$$$.

Вы дали НЛО массив $$$a$$$ длиной $$$n$$$. Чтобы поблагодарить вас, НЛО решает построить другой массив $$$b$$$ длиной $$$n$$$ так, чтобы $$$a_i$$$ была модой последовательности $$$[b_1, b_2, \ldots, b_i]$$$ для всех $$$1 \leq i \leq n$$$.

Однако НЛО не знает, как построить массив $$$b$$$, поэтому вы должны ей помочь. Обратите внимание, что для вашего массива должно выполняться условие $$$1 \leq b_i \leq n$$$ для всех $$$1 \leq i \leq n$$$.

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

Первая строка содержит $$$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$$$ ($$$1 \leq a_i \leq n$$$).

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

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

Для каждого набора входных данных выведите $$$n$$$ чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$) в новой строке. Можно показать, что массив $$$b$$$ всегда можно построить. Если существует несколько возможных массивов, вы можете вывести любой из них.

Пример
Входные данные
4
2
1 2
4
1 1 1 2
8
4 5 5 5 1 1 2 1
10
1 1 2 2 1 1 3 3 1 1
Выходные данные
1 2
1 1 2 2
4 5 5 1 1 2 2 3
1 8 2 2 1 3 3 9 1 1
Примечание

Давайте проверим корректность нашего образца вывода в наборе входных данных $$$2$$$

  • При $$$i = 1$$$, $$$1$$$ является единственной возможной модой для $$$[1]$$$.
  • При $$$i = 2$$$, $$$1$$$ является единственной возможной модой для $$$[1, 1]$$$.
  • При $$$i = 3$$$, $$$1$$$ является единственной возможной модой для $$$[1, 1, 2]$$$.
  • При $$$i = 4$$$, $$$1$$$ или $$$2$$$ могут считаться модой для $$$[1, 1, 2, 2]$$$. Поскольку $$$a_i = 2$$$, этот массив является допустимым.