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

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