Вам дан массив \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач