C. k-удивительные числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Назовем $$$k$$$-удивительным числом массива минимальное число, которое встречается во всех подмассивах длины $$$k$$$ (напомним, что подмассивом массива $$$a$$$ длины $$$k$$$ называются $$$k$$$ подряд идущих элементов массива $$$a$$$). Если для некоторого $$$k$$$ не существует ни одного числа, встречающегося во всех подмассивах длины $$$k$$$, то $$$k$$$-удивительным числом считается $$$-1$$$.

Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ найдите $$$k$$$-удивительное число массива $$$a$$$.

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

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длина массива. Вторая строка набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.

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

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

Для каждого набора тестовых данных выведите $$$n$$$ целых чисел, где $$$i$$$-е число является $$$i$$$-удивительным числом массива.

Пример
Входные данные
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1
Выходные данные
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1