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