Вам дан массив \(a\) из \(n\) целых чисел, пронумерованных от \(1\) до \(n\).
Назовем \(k\)-удивительным числом массива минимальное число, которое встречается во всех подмассивах длины \(k\) (напомним, что подмассивом массива \(a\) длины \(k\) называются \(k\) подряд идущих элементов массива \(a\)). Если для некоторого \(k\) не существует ни одного числа, встречающегося во всех подмассивах длины \(k\), то \(k\)-удивительным числом считается \(-1\).
Для каждого \(k\) от \(1\) до \(n\) найдите \(k\)-удивительное число массива \(a\).
Выходные данные
Для каждого набора тестовых данных выведите \(n\) целых чисел, где \(i\)-е число является \(i\)-удивительным числом массива.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|