codeforces#P1132G. Greedy Subsequences
Greedy Subsequences
Description
For some array $c$, let's denote a greedy subsequence as a sequence of indices $p_1$, $p_2$, ..., $p_l$ such that $1 \le p_1 < p_2 < \dots < p_l \le |c|$, and for each $i \in [1, l - 1]$, $p_{i + 1}$ is the minimum number such that $p_{i + 1} > p_i$ and $c[p_{i + 1}] > c[p_i]$.
You are given an array $a_1, a_2, \dots, a_n$. For each its subsegment of length $k$, calculate the length of its longest greedy subsequence.
The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$) — the length of array $a$ and the length of subsegments.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — array $a$.
Print $n - k + 1$ integers — the maximum lengths of greedy subsequences of each subsegment having length $k$. The first number should correspond to subsegment $a[1..k]$, the second — to subsegment $a[2..k + 1]$, and so on.
Input
The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$) — the length of array $a$ and the length of subsegments.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — array $a$.
Output
Print $n - k + 1$ integers — the maximum lengths of greedy subsequences of each subsegment having length $k$. The first number should correspond to subsegment $a[1..k]$, the second — to subsegment $a[2..k + 1]$, and so on.
Samples
6 4
1 5 2 5 3 6
2 2 3
7 6
4 5 2 5 3 6 6
3 3
Note
In the first example:
- $[1, 5, 2, 5]$ — the longest greedy subsequences are $1, 2$ ($[c_1, c_2] = [1, 5]$) or $3, 4$ ($[c_3, c_4] = [2, 5]$).
- $[5, 2, 5, 3]$ — the sequence is $2, 3$ ($[c_2, c_3] = [2, 5]$).
- $[2, 5, 3, 6]$ — the sequence is $1, 2, 4$ ($[c_1, c_2, c_4] = [2, 5, 6]$).
In the second example:
- $[4, 5, 2, 5, 3, 6]$ — the longest greedy subsequences are $1, 2, 6$ ($[c_1, c_2, c_6] = [4, 5, 6]$) or $3, 4, 6$ ($[c_3, c_4, c_6] = [2, 5, 6]$).
- $[5, 2, 5, 3, 6, 6]$ — the subsequence is $2, 3, 5$ ($[c_2, c_3, c_5] = [2, 5, 6]$).