JOI mart is a shop which has ~N~ days of history. After opening JOI mart, the sales amount on the ~i~-th day ~(1 \le i \le N)~ was ~A_i~ yen.

Bitaro is a shop manager of JOI mart, who will make a presentation of the financial report. For the presentation, he will choose some of the days, and show a bar chart of the sales amounts for the chosen days in chronological order. He will explain how the sales amounts changed for these days. In order to make the presentation much more impressive, he plans to choose the data for the presentation so that the presentation would give a better impression.

If Bitaro chooses the data of sales amounts for ~m~ days ~(1 \le m \le N)~ and he chooses the data of the ~p_1, p_2, \dots, p_m~-th days ~(1 \le p_1 < p_2 < \dots < p_m \le N)~ after opening, the impression score of a bar chart is calculated as follows.

The impression score is equal to the number of times of making record-high sales amounts among the chosen days. In other words, the impression score is equal to the number of the indices ~j~ ~(1 \le j \le m)~ satisfying ~j = 1~ or ~\max\{A_{p_1}, A_{p_2}, \dots, A_{p_{j-1}}\} < A_{p_j}~.

Bitaro wants to maximize the impression score, but the presentation might be unnatural for some choice of data. Thus, he decided to choose data satisfying both of the following conditions.

• Bitaro will show the latest sales amount. In other words, ~p_m = N~ is satisfied.
• For any two consecutive data for the presentation, the difference of the dates is at most ~D~ days. In other words, if ~m \ge 2~, the inequality ~p_{j+1}-p_j \le D~ is satisfied for every ~j~ ~(1 \le j \le m-1)~.

Write a program which, given the data of sales amounts of JOI mart after opening and an integer ~D~, calculate the maximum of the impression score of a bar chart for the presentation.

Input Specification

Read the following data from the standard input. Given values are all integers.

~N\ D~

~A_1 \dots A_N~

Output Specification

Write one line to the standard output. The output should contain the maximum of the impression score of a bar chart for the presentation.

Constraints

• ~1 \le N \le 300\,000~.
• ~1 \le D \le N~.
• ~0 \le A_i \le 1\,000\,000\,000~ ~(1 \le i \le N)~.

Subtasks

1. (14 points) ~N \le 20~.
2. (14 points) ~N \le 400~.
3. (20 points) ~N \le 7\,000~.
4. (12 points) ~D = 1~.
5. (5 points) ~D = N~.
6. (35 points) No additional constraints.

Sample Input 1

7 1
100 600 600 200 300 500 500

Sample Output 1

3

Explanation for Sample 1

In this sample input, there are ~7~ possibilities for a bar chart for the presentation satisfying the conditions in the task statement.

• If Bitaro shows a bar chart of the data of the ~1, 2, 3, 4, 5, 6, 7~-th days from opening, the impression score is ~2~ points.
• If Bitaro shows a bar chart of the data of the ~2, 3, 4, 5, 6, 7~-th days from opening, the impression score is ~1~ point.
• If Bitaro shows a bar chart of the data of the ~3, 4, 5, 6, 7~-th days from opening, the impression score is ~1~ point.
• If Bitaro shows a bar chart of the data of the ~4, 5, 6, 7~-th days from opening, the impression score is ~3~ points.
• If Bitaro shows a bar chart of the data of the ~5, 6, 7~-th days from opening, the impression score is ~2~ points.
• If Bitaro shows a bar chart of the data of the ~6, 7~-th days from opening, the impression score is ~1~ point.
• If Bitaro shows a bar chart of the data of the ~7~-th day from opening, the impression score is ~1~ point.

Therefore, the maximum of the impression score is ~3~ points. Your program is considered correct if it outputs ~3~.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 6.

Sample Input 2

6 6
100 500 200 400 600 300

Sample Output 2

4

Explanation for Sample 2

In this sample input, the maximum impression score is achieved if Bitaro shows a bar chart of the data of the ~1, 3, 4, 5, 6~-th days from opening. If these days are chosen, the sales amounts of the chosen days are ~100, 200, 400, 600, 300~ yen. Since the number of times of making record-high sales amounts among the chosen data is ~4~, the impression score is ~4~ points. Thus, output ~4~.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 5, 6.

Sample Input 3

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

Sample Output 3

4

Explanation for Sample 3

In this sample input, the maximum impression score is achieved if Bitaro shows a bar chart of the data of the ~1, 3, 5, 6, 8, 9, 11~-th days from opening, for example. If these days are chosen, the sales amounts of the chosen days are ~1, 4, 2, 4, 5, 7, 3~ yen. Since number of times of making record-high sales amounts among the chosen data is ~4~, the impression score is ~4~ points. Thus, output ~4~. Note that, in this sample input, there are several ways to choose the data satisfying the conditions in the task statements for which the impression score is ~4~ points.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 6.