P7804 [JOI Open 2021] Financial Report / Financial Report

**Warning: Abusing the judge for this problem will result in your account being banned.**

There is a sequence $A_i$ of length $N$. Define the value of the function $f(m,p_1,p_2,\cdots,p_m)$ as the number of indices $p_i$ that satisfy: $$\max\limits_{j=1}^{i-1}\{A_{p_j}\} < A_{p_i}$$ When $i=1$, we assume that the inequality above always holds. Given an integer $D$, find a sequence $p_i$ that satisfies: - $1 \le m \le N$; - $p_m = N$; - $p_i < p_{i+1}$; - If $m \ge 2$, then $p_{j+1} - p_j \le D$; - The value of $f(m,p_1,p_2,\dots,p_m)$ is maximized. Output the maximum value of the function $f$.

The first line contains two integers $N, D$, with the meaning as described in the statement. The second line contains $N$ integers $A_i$, representing the given sequence.

Output one integer on a single line, representing the maximum value of the function $f$.

#### Sample 1 Explanation There are $7$ possible cases in total: - $p_i=\{1,2,3,4,5,6,7\}$, $f(7,1,2,3,4,5,6,7)=2$; - $p_i=\{2,3,4,5,6,7\}$, $f(6,2,3,4,5,6,7)=1$; - $p_i=\{3,4,5,6,7\}$, $f(5,3,4,5,6,7)=1$; - $p_i=\{4,5,6,7\}$, $f(4,4,5,6,7)=3$; - $p_i=\{5,6,7\}$, $f(3,5,6,7)=2$; - $p_i=\{6,7\}$, $f(2,6,7)=1$; - $p_i=\{7\}$, $f(1,7)=1$. The maximum value is $3$. #### Sample 2 Explanation The optimal $p_i=\{1,3,4,5,6\}$. The corresponding $A_i=\{100,200,400,600,300\}$, and the value of $f$ is $4$. #### Sample 3 Explanation There are multiple optimal ways. One of them is $p_i=\{1,3,5,6,8,9,11\}$. The corresponding $A_i=\{ 1, 4, 2, 4, 5, 7, 3\}$, and the value of $f$ is $4$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (14 pts): $N \le 20$; - Subtask 2 (14 pts): $N \le 400$; - Subtask 3 (20 pts): $N \le 7000$; - Subtask 4 (12 pts): $D = 1$; - Subtask 5 (5 pts): $D = N$; - Subtask 6 (35 pts): no special restrictions. For $100\%$ of the testdata: - $1 \le N \le 3 \times 10^5$; - $1 \le D \le N$; - $0 \le A_i \le 10^9$. #### Notes Translated from [JOI 2020 / 2021 Open Contest B Financial Report](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2021/financial/2021-open-financial-statement-en.pdf). Translated by ChatGPT 5