CF1132G.Greedy Subsequences

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 \lt p_2 \lt \dots \lt p_l \le |c|$, and for each $i \in [1, l - 1]$, $p_{i + 1}$ is the minimum number such that $p_{i + 1} \gt p_i$ and $c[p_{i + 1}] \gt 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.

对于某个数组 $c$，我们定义其“贪心子序列”为一组下标序列 $p_1, p_2, \dots, p_l$，满足 $1 \le p_1 \lt p_2 \lt \dots \lt p_l \le |c|$，且对每个 $i \in [1, l - 1]$，$p_{i + 1}$ 是满足 $p_{i + 1} \gt p_i$ 且 $c[p_{i + 1}] \gt c[p_i]$ 的最小下标。

给定一个数组 $a_1, a_2, \dots, a_n$。对它的每一个长度为 $k$ 的连续子段，计算该子段的最长贪心子序列的长度。

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$.

第一行包含两个整数 $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$。

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.

输出 $n - k + 1$ 个整数——每个长度为 $k$ 的子段的贪心子序列的最大长度。第一个数对应子段 $a[1..k]$，第二个数对应子段 $a[2..k + 1]$，依此类推。

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]$).

在第一个例子中：

• $[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]$）。