'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 2 numbers separated by a space: 1 <= N, M <= 1000, which are the Number of cars in the lot and the Maximum distance the guards can see in the fog. The following N lines will contain a single integer 1 <= H <= 1000, the Height of each car, in order.
The output file OUT5.txt will contain 5 lines of output. Each line 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
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 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.