DWITE, November 2012, Problem 5

'Car hopping' is a common pastime of programmers that involves them hopping atop of cars parked in a lot (it gives them something to do while waiting for their code to compile). After having received multiple complaints, the parking lot company decided to hire guards to stand on top of cars to prevent programmers from car hopping. However, there are certain factors the guards should take into account:

• In the lot that they are guarding there are $N$ cars in a row, each of a certain height.
• Due to the heavy fog in the area, the guards can only monitor the tops of the cars that are up to $S$ spots away from them.
• No guard can see past a car (no matter how close it is to them) that has a height greater than the car they are standing on.

Given the predicament they are in, the company decides to hire a programmer (one of the founders of 'Car hopping' nonetheless!) to help them determine the minimum number of guards needed.

The input will contain 5 test cases. The first line of each test case contains 2 numbers, separated by a space $1\le N,M\le 1000$. These represent the number of cars in the lot and the maximum distance the guards can see in the fog, respectively. The following $N$ lines will contain a single integer $1\le H\le 1000$, the height of each car, in order.

The output will contain 5 lines of output. Each line contains a single integer, representing the minimum number of guards necessary to monitor the lot for each corresponding case.

Sample Input

5 2
2
2
2
2
2
5 2
2
1
3
4
1

Sample Output

1
2

Problem Resource: DWITE