“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 file DATA5.txt will contain 5 test cases. The first line of each test case contains two numbers separated by a space: 1 ≤ N, M ≤ 1000, which are the (N)umber of cars in the lot and the (M)aximum distance the guards can see in the fog. The following N lines will each contain a single integer 1 ≤ H ≤ 1000, the (H)eight of the car, in order.
The output file OUT5.txt will contain 5 lines. Each is a single integer representing the minimum number of guards necessary to monitor the parking lot for the corresponding case.
5 2
2
2
2
2
2
5 2
2
1
3
4
1
1
2
Notes: In the first case, a single guard can be placed on the middle car, and the range of 2 in each direction will cover the entire lot. In the second case, such a strategy will not work, as a guard in the middle (height 3) is blocked by the following car (height 4) from monitoring the last car of the lot.