Problem Description

There is a sequence \( A_i \) of length \( N \). Define the function \( f(m, p_1, p_2, \cdots, p_m) \) as the count of \( p_i \) such that:

\[ \max_{j=1}^{i-1} \{ A_{p_j} \} < A_{p_i} \]

When \( i = 1 \), we assume the inequality 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 \);
• \( f(m, p_1, p_2, \dots, p_m) \) is maximized.

Determine the maximum value of the function \( f \).

Input Format

The first line contains two integers \( N \) and \( D \), as described in the problem statement.

The second line contains \( N \) integers \( A_i \) representing the given sequence.

Output Format

Output a single integer representing the maximum value of the function \( f \).

Sample Input and Output

Input Example #1

7 1
100 600 600 200 300 500 500

Output Example #1

3

Input Example #2

6 6
100 500 200 400 600 300

Output Example #2

4

Input Example #3

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

Output Example #3

4

Notes

Sample 1 Explanation

There are 7 possible cases:

• \( 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\} \), corresponding to \( A_i = \{100, 200, 400, 600, 300\} \), with \( f \) value of 4.

Sample 3 Explanation

There are multiple optimal ways, one of which is \( p_i = \{1, 3, 5, 6, 8, 9, 11\} \), corresponding to \( A_i = \{1, 4, 2, 4, 5, 7, 3\} \), with \( f \) value of 4.

Data Constraints

This problem is bundled.

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

For 100% of the data:

• \( 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.

见题面 Input 部分

见题面 Output 部分