样例下载

题目描述

二维平面直角坐标系中有 N 个点，第 i 个点的坐标为 $(i, Y_i)$。

现在要从中选择若干个点，其中第 1 个点和第 N 个点必选，并且要求所选的任意相邻两个点的水平距离不能超过 M。然后对于所选出的点，在相邻的两个点之间连线，这样会形成一条折线，要求折线上方不能出现点（点可以出现在折线上，不能出现在折线上方）。

问：你最少需要选择多少个点？

输入格式

第一行：包含两个整数 $N, M$。

接下来 N 行，每行一个整数 $Y_i$

输出格式

一个整数，表示答案。

样例输入

10 4
0
1
0
1
5
6
8
6
8
8

样例输出

4

样例解释

选第 1, 5, 7, 10 四个点

数据范围

$2 ≤ N ≤ 5000, 1 ≤ M ≤ N−1, 0 ≤ Y_i ≤ 10^9$。