Maximize Increasing Record Count under Gap Constraint

You are given a sequence \(A_1, A_2, \dots, A_N\) of length \(N\) and an integer \(D\). We define the function \(f(m, p_1, p_2, \dots, p_m)\) as the number of indices \(p_i\) satisfying

\(\max\limits_{j=1}^{i-1} \{A_{p_j}\} < A_{p_i}\)

with the convention that when \(i=1\) the inequality is considered to be always true.

Your task is to choose a sequence of indices \(p_1, p_2, \dots, p_m\) which satisfies the following conditions:

• \(1 \le m \le N\).
• \(p_m = N\) (i.e. the sequence must end at index \(N\)).
• The indices are strictly increasing: \(p_i < p_{i+1}\).
• If \(m \ge 2\), then the gap between consecutive indices is at most \(D\), i.e., \(p_{j+1} - p_j \le D\) for all valid \(j\).
• The function \(f(m, p_1, p_2, \dots, p_m)\) is maximized, where an index \(p_i\) (with \(i \ge 2\)) contributes to the count only if \(A_{p_i}\) is greater than all previously chosen \(A_{p_j}\) (and \(p_1\) always contributes).

Output the maximum value of \(f\) that can be obtained by any such sequence.

inputFormat

The first line contains two integers \(N\) and \(D\) separated by a space.

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\), separated by spaces.

outputFormat

Output a single integer representing the maximum value of \(f(m, p_1, p_2, \dots, p_m)\) attainable subject to the given conditions.

sample

5 2
1 2 3 4 5

5