G. Жадные подпоследовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$c$$$ назовем жадной подпоследовательностью последовательность индексов $$$p_1$$$, $$$p_2$$$, ..., $$$p_l$$$, такую, что $$$1 \le p_1 < p_2 < \dots < p_l \le |c|$$$, и для всех $$$i \in [1, l - 1]$$$, $$$p_{i + 1}$$$ — минимальный индекс, для которого выполняются условия: $$$p_{i + 1} > p_i$$$ и $$$c[p_{i + 1}] > c[p_i]$$$.

Вам дан массив $$$a_1, a_2, \dots, a_n$$$. Для каждого его подотрезка длины $$$k$$$ посчитайте длину его самой длинной жадной подпоследовательности.

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

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 10^6$$$) — длина массива $$$a$$$ и длина подотрезков.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — массив $$$a$$$.

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

Выведите $$$n - k + 1$$$ чисел — максимальные длины жадных подпоследовательностей для каждого подотрезка длины $$$k$$$. Первое число должно быть ответом для подотрезка $$$a[1..k]$$$, второе — для $$$a[2..k + 1]$$$, и так далее.

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

В первом примере:

  • $$$[1, 5, 2, 5]$$$ — наидлиннейшими являются подпоследовательности $$$1, 2$$$ ($$$[c_1, c_2] = [1, 5]$$$) или $$$3, 4$$$ ($$$[c_3, c_4] = [2, 5]$$$).
  • $$$[5, 2, 5, 3]$$$ — подпоследовательность $$$2, 3$$$ ($$$[c_2, c_3] = [2, 5]$$$).
  • $$$[2, 5, 3, 6]$$$ — подпоследовательность $$$1, 2, 4$$$ ($$$[c_1, c_2, c_4] = [2, 5, 6]$$$).

Во втором примере:

  • $$$[4, 5, 2, 5, 3, 6]$$$ — наидлиннейшими являются подпоследовательности $$$1, 2, 6$$$ ($$$[c_1, c_2, c_6] = [4, 5, 6]$$$) или $$$3, 4, 6$$$ ($$$[c_3, c_4, c_6] = [2, 5, 6]$$$).
  • $$$[5, 2, 5, 3, 6, 6]$$$ — подпоследовательность $$$2, 3, 5$$$ ($$$[c_2, c_3, c_5] = [2, 5, 6]$$$).