Description

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:

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

Input Format

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 Format

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

7 1
100 600 600 200 300 500 500

3

6 6
100 500 200 400 600 300

4

11 2
1 4 4 2 2 4 9 5 7 0 3

4

Hint

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.

Translated by ChatGPT 5