[Usaco2006 Mar]Ski Lift 缆车支柱

科罗拉州的罗恩打算为奶牛们建造一座滑雪场。由于预算有限，滑雪场只会修建一部缆车。

罗恩在缆车经过的山坡上选取了 $N$ 个水平间距均为 $1$ 个单位长度的测量点，并记录了每个点的整数高度 $H_i$。地面轮廓由依次连接相邻测量点的线段组成。

缆车由若干根修建在测量点上的支柱以及连接相邻支柱的笔直钢丝构成。支柱相对于所在地面的高度可以忽略不计。若在第 $i$ 个点和第 $j$ 个点之间连接钢丝，则该钢丝必须始终位于地面之上或恰好与地面相切。等价地，这条钢丝不能低于第 $i$ 个点与第 $j$ 个点之间的任何测量点。

根据安全规定，任意两根相邻支柱的水平距离不能超过 $K$ 个单位长度。此外，第 $1$ 个点和第 $N$ 个点上必须修建支柱。

请计算满足上述条件时，罗恩最少需要修建多少根支柱。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$。

接下来 $N$ 行，第 $i$ 行包含一个整数 $H_i$，表示第 $i$ 个测量点的高度。

输出格式

输出一个整数，表示最少需要修建的支柱数量。

样例输入

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

样例输出

5

样例解释

最少需要修建 $5$ 根支柱，分别位于第 $1$、$5$、$7$、$9$ 和 $13$ 个测量点。相邻支柱之间的钢丝均位于地面之上或与地面相切，且水平距离均不超过 $K$。

数据范围

• $2\le N\le 5000$；
• $1\le K\le N-1$；
• $0\le H_i\le 10^9$，且所有高度均为整数。

来源与许可

本题为 USACO 2006 March 试题「Ski Lift 缆车支柱」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

5