Для массива \(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\) чисел — максимальные длины жадных подпоследовательностей для каждого подотрезка длины \(k\). Первое число должно быть ответом для подотрезка \(a[1..k]\), второе — для \(a[2..k + 1]\), и так далее.
Примечание
В первом примере:
- \([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]\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 4
1 5 2 5 3 6
|
2 2 3
|
|
2
|
7 6
4 5 2 5 3 6 6
|
3 3
|