题目描述

伟大钱是一名地理学家，创立了“蒋迪有奖励”公众号，某天，伟大的望梅问校长找到了他，让他为 cyyz 铺设一条长度为 $n$ 的道路。

铺设道路的主要工作是填平凹凸不平的地表。整段道路可以看作是 $n$ 块首尾相连的区域，一开始，第 $i$ 块区域的高度为 $d_i$ 。

伟大钱每天可以选择一段连续区间 $[L,R]$ ，让其高度增加或减少 $1$ 。

但是事情总不尽如人意。伟大的生物学家柳杰鬓曾经说过："咱们这个食堂，它不是吃饭的地方。"

伟大钱由于吃了 cyyz 食堂的饭，成功地窜稀了。

伟大钱捂住肚子找到你，希望你能帮他设计一种方案，可以在最短的时间内使得整段道路相邻两个位置的高度差的绝对值都小于等于 $k$ 。注意第 $1$ 个和第 $0$ 个位置以及第 $n$ 个和第 $n+1$ 个位置的高度差的绝对值也不能大于 $k$ 。在这里，我们认为第 $0$ 个位置和第 $n+1$ 个位置的高度是 $0$ 且不能被更改。

作为 cyyz 最会修电脑的信息学后备人才，请你帮助伟大钱解决这个问题，作为回报，他会送给你“蒋迪有奖励”公众号所有付费阅读的文章终身免费资格。

输入格式

输入包含两行。

第一行包含两个整数 $n,k$ ，表示道路的长度和最大高度差。

第二行包含 $n$ 个整数，相邻两数间用一个空格隔开，第$i$个整数为 $d_i$ 。

输出格式

输出仅包含一个整数，即最少需要多少天才能完成任务。

6 1
4 3 2 5 3 5

6

样例解释

一种可行的最佳方案是，依次选择： $[1,6] - 1$、$[1,6] - 1$、$[1,6] - 1$、$[6,6] - 1$、$[4,4] - 1$、$[4,4] - 1$。

样例2

见选手目录下的 qdw/qdw.in 和 qdw/qdw.out。

数据规模与约定

对于$30\%$的数据，$1≤n≤10$ ；

对于另外$30\%$的数据，$k=0$ ；

对于$100\%$的数据，$1≤n≤100000,-100000≤ d_i≤100000,0\le k\le 100000$ 。