JOI mart is a shop which has days of history. After opening JOI mart, the sales amount on the -th day was 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 days and he chooses the data of the -th days 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 satisfying or .
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, is satisfied.
- For any two consecutive data for the presentation, the difference of the dates is at most days. In other words, if , the inequality is satisfied for every .
Write a program which, given the data of sales amounts of JOI mart after opening and an integer , 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.
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
- .
- .
- .
Subtasks
- (14 points) .
- (14 points) .
- (20 points) .
- (12 points) .
- (5 points) .
- (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 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 -th days from opening, the impression score is points.
- If Bitaro shows a bar chart of the data of the -th days from opening, the impression score is point.
- If Bitaro shows a bar chart of the data of the -th days from opening, the impression score is point.
- If Bitaro shows a bar chart of the data of the -th days from opening, the impression score is points.
- If Bitaro shows a bar chart of the data of the -th days from opening, the impression score is points.
- If Bitaro shows a bar chart of the data of the -th days from opening, the impression score is point.
- If Bitaro shows a bar chart of the data of the -th day from opening, the impression score is point.
Therefore, the maximum of the impression score is points. Your program is considered correct if it outputs .
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 -th days from opening. If these days are chosen, the sales amounts of the chosen days are yen. Since the number of times of making record-high sales amounts among the chosen data is , the impression score is points. Thus, output .
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 -th days from opening, for example. If these days are chosen, the sales amounts of the chosen days are yen. Since number of times of making record-high sales amounts among the chosen data is , the impression score is points. Thus, output . 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 points.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 6.
Comments