Squeaky the Mouse 最近对视觉艺术产生了兴趣，并正在尝试创作自己的艺术作品，以便在镇上最负盛名的视觉艺术节上展出。

他的艺术作品由许多大小相同的发光立方体堆叠而成，排成一行。更准确地说，共有 $N$ 堆立方体，从左到右编号为 $1$ 到 $N$，第 $i$ 堆包含 $S[i]$ 个立方体。以下是 Squeaky 艺术作品的一种可能形态：

图 5：可能的艺术作品配置，$N = 20$

由于立方体非常沉重，组装这些立方体来构成艺术作品是一项非常耗力的工作，Squeaky 仅在艺术节开始前几天才完成了组装。

就在他以为终于可以休息一下时，安全委员会来评估他的艺术作品。自去年艺术节发生了一次灾难性的事故以来，该艺术节的安全委员会一直非常挑剔且毫不妥协。

当 Squeaky 看到委员会成员聚在一起低声交谈时，他的心沉了下去。他知道他们发现了作品的问题。最终，委员会的一些成员走近他，解释了他们的担忧：当游客撞到艺术作品时，一些堆叠可能会倒塌。具体来说，只有当相邻堆叠的高度差不超过 $H$ 个立方体时，艺术作品才是安全的；即对于所有 $1 \le i \le N - 1$，满足 $|S[i] - S[i + 1]| \le H$。

他们给了他两个选择——要么修改艺术作品使其变得安全，要么完全拆除艺术作品。

当然，在这一作品上花费了如此多的心血，Squeaky 根本不考虑拆除艺术作品，因此他选择通过添加和移除一些立方体来修改艺术作品。由于搬运立方体很累，他希望尽量减少他需要做的工作量。

形式上，他希望最小化使艺术作品变得安全所需的步骤数，其中每一步都是以下操作之一：

• 在第 $k$ 堆的顶部添加一个立方体，其中 $1 \le k \le N$
• 从第 $k$ 堆的顶部移除一个立方体，其中 $1 \le k \le N$

请帮助 Squeaky 确定他使艺术作品变得安全所需的最少步骤数。

输入格式

你的程序必须从标准输入读取数据。

第一行包含两个正整数 $N$ 和 $H$。

第二行包含 $N$ 个非负整数。该行中的第 $i$ 个整数为 $S[i]$。

输出格式

你的程序必须写入标准输出。

你的程序必须输出一个整数——使艺术作品变得安全所需的最少操作次数。

子任务

每个实例的最大执行时间为 1.0 秒。

对于所有实例，输入将满足以下约束：

• $1 \le N \le 200\,000$
• $0 \le H \le 1\,000\,000\,000$
• $0 \le S[i] \le 1\,000\,000\,000$，对于所有 $1 \le i \le N$

你的程序将在以下输入实例集合上进行测试：

样例

样例输入 1

6 1
2 10 0 2 4 3

样例输出 1

10

说明 1

图 6：样例 1 的可能解决方案。左侧为原始艺术作品；右侧为修改后的艺术作品。红色高亮的立方体表示需要从原始艺术作品中移除的立方体；黄色高亮的立方体表示需要添加到修改后艺术作品中的立方体。

上图展示了一种使艺术作品变得安全的方法。该艺术作品是安全的，因为每对相邻堆叠的高度差不超过 1。

这需要十个步骤（红色和黄色高亮的立方体总数）。由于没有其他使艺术作品变得安全且步骤少于十的方法，因此正确输出为 10。注意，可能存在其他同样需要十个步骤的方案。

样例输入 2

6 3
2 10 2 6 4 3

样例输出 2

6

说明 2

图 7：样例 2 的可能解决方案。

至少需要六个步骤才能使艺术作品变得安全。因此，正确输出为 6。

样例输入 3

4 1
1 4 1 4

样例输出 3

4

说明 3

图 8：样例 3 的可能解决方案。

至少需要四个步骤才能使艺术作品变得安全。因此，正确输出为 4。

样例输入 4

10 1
10 9 8 7 6 5 4 3 2 1

样例输出 4

0

说明 4

图 9：样例 4 中的艺术作品。

该艺术作品已经是安全的，因此无需进行任何修改。因此，答案为 0。

样例输入 5

3 0
1 1 3

样例输出 5

2

说明 5

图 10：样例 5 的可能解决方案。

至少需要两个步骤才能使艺术作品变得安全。因此，正确输出为 2。