'Car hopping' is a common past-time 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 <= N M <= 1000. 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. A single integer, representing the minimum number of guards necessary to monitor the lot for each 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.