对于某些数组 $$$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]$$$,依此类推。
示例
输入 #1
6 4 1 5 2 5 3 6
输出 #1
2 2 3
输入 #2
7 6 4 5 2 5 3 6 6
输出 #2
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]$$$)。