Задача с собеседования

Ограничение времени1 секунда
Ограничение памяти256 Мб
Вводстандартный ввод
Выводстандартный вывод

Одним из шагов отбора в IT-компании является собеседование с решением алгоритмических задач. От задач на олимпиадах они отличаются отсутствием «легенды» и содержат формальное условие, а в остальном очень похожи. Например, задача может быть такой:

«Дана последовательность целых чисел a 1 , a 2 , , a n a_1, a_2, \ldots, a_n . Для каждых k k подряд идущих элементов необходимо найти максимальное число среди тех, которые встречаются на этом подотрезке строго один раз, или сообщить, что на подотрезке уникальных чисел нет.»

Напишите решение этой задачи на одном из допустимых языков программирования.

Формат ввода

В первой строке записаны целых числа n n и k k ( 1 k n 1 0 5 1 \leq k \leq n \leq 10^5 )  — длина последовательности и длины рассматриваемых подотрезков.

Во второй строке записано n n целых положительных чисел a 1 , a 2 , , a n a_1, a_2, \ldots, a_n ( 1 a i 1 0 9 1 \leq a_i \leq 10^9 )  — последовательность a a .

Формат вывода

Выведите n k + 1 n-k+1 строк. В i i -й строке будет содержаться максимальный уникальный элемент среди чисел a i , a i + 1 , , a i + k 1 a_{i}, a_{i+1}, \ldots, a_{i+k-1} или 1 -1 , если среди чисел нет уникальных.

Пример 1

ВводВывод
5 3
2 3 3 4 4
2 4 3 

Пример 2

ВводВывод
6 4
2 2 2 3 3 1
3 -1 2 

Примечания

Оценка за эту задачу — 100 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).