题目描述

科罗拉多州的山脉是二维平面上的一条折线。这条折线由 $N$ 个端点，$N−1$ 段线段组成，第 $i$ 个端点的横坐标就是 $i$，纵坐标是 $H_i$，纵坐标代表高度，也可以称为海拔。

罗恩打算为奶牛建造一个滑雪场，为此要在山脉上规划一条缆车线路。缆线也是一条折线，由若干段缆绳组成，起点在山脉的第一个端点，终点在最后一个端点。每段缆绳可以贴着山脉的轮廓，也可以悬浮于空中，跳过山脉上几个海拔低的端点。每段缆绳的水平跨度有限制，不能超过给定的整数 $K$。罗恩需要在每段缆绳的端点处修建支柱，用来固定缆绳。

请帮助他规划一下，选择在山脉的哪些端点上修建，才能使得支柱数量最少？注意，根据题意，起点和终点上是一定要修建的。

输入格式

第一行：两个整数 $N$ 和 $K$。

第二行到第 $N + 1$ 行，第 $i+1$ 行有一个整数 $H_i$。

输出格式

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

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

5

提示

解释 最优方案是把支柱设在 $1,5,7,9,13$。$5$ 不能直接连 $9$，因为 $9$ 的海拔较高，$1$ 不能直接连 $7$，因为跨度超过了 $K$。

数据范围

$2 \le N \le 5000$，$1 \le K \le N − 1$，$0\le H_i \le 10^9$。