- Описание
- Отправленные решения
22. Минимум на отрезке
Рассмотрим последовательность целых чисел длины $n$.
По ней двигается «окно» длины $k$: сначала в «окне» находятся первые $k$ чисел, на следующем шаге в «окне» уже будут находиться $k$ чисел, начиная со второго, и так далее до конца последовательности.
Требуется для каждого положения «окна» определить минимум в нём.
Формат ввода
В первой строке входных данных содержатся два натуральных числа $n$ и $k$ ($n \le 150\,000$, $k \le 10\,000$, $k \le n$) — длины последовательности и «окна», соответственно.
На следующей строке находятся $n$ целых чисел — сама последовательность.
Формат вывода
Выведите $n - k + 1$ строк. В каждой строке должно быть одно число — минимум для соответствующего положения «окна».
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
Ввод
7 3
1 3 2 4 5 3 1
Вывод
1
2
2
3
1