Description

The mountains of Colorado are represented as a polyline in the 2D plane. This polyline has $N$ endpoints and $N - 1$ segments. The $i$-th endpoint has x-coordinate $i$ and y-coordinate $H_i$. The y-coordinate represents altitude (elevation).

Ron plans to build a ski resort for the cows, and needs to plan a ski lift line along the mountains. The cable line is also a polyline, composed of several cable segments, starting at the first mountain endpoint and ending at the last endpoint. Each cable segment can either follow the outline of the mountain or be suspended in the air, skipping several endpoints with lower altitude. The horizontal span of each cable segment is limited and cannot exceed the given integer $K$. Ron must build pillars at the endpoints of each cable segment to fasten the cable.

Please help him plan which mountain endpoints should have pillars so that the number of pillars is minimized. Note that, by the problem statement, the start and end endpoints must have pillars.

Constraints $2 \le N \le 5000$, $1 \le K \le N - 1$, $0 \le H_i \le 10^9$.

Input Format

The first line contains two integers $N$ and $K$.

Lines $2$ through $N + 1$: line $i + 1$ contains an integer $H_i$.

Output Format

Output a single integer, the minimum number of pillars required.

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

5

Hint

Explanation: The optimal plan is to place pillars at $1, 5, 7, 9, 13$. $5$ cannot directly connect to $9$ because the altitude at $9$ is higher; $1$ cannot directly connect to $7$ because the span exceeds $K$.

Translated by ChatGPT 5