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.

N/A

N/A

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