题目背景

译自 NOISG 2018 Finals E. Safety。

题目描述

小老鼠 Squeaky 最近开始欣赏视觉艺术，并尝试创作自己的艺术作品，在城里最负盛名的艺术节上展出！

他的作品由若干发光柱组成，其中每个发光柱又都是由发光立方体堆砌而成的。

具体来说，他的作品是排成一条直线的 $N$ 个发光柱，从左到右编号为 $1$ 到 $N$。其中第 $i$ 个发光柱的高度为 $S_i$，意味着它由 $S_i$ 个发光立方体堆砌而成。

例如下图是 $N=20$ 时一种可能的作品：

然而，观众撞到不安全的展品将造成灾难性的后果。所以，安全委员会要求 Squeaky 保证作品的安全性。具体来说，作品安全当且仅当任意两个相邻发光柱的高度差不超过 $H$，即 $|S_i-S_{i+1}|\le H,\forall i\in[1,N)$。

Squeaky 的作品可能是不安全的，为了确保正常展出，他希望通过修改作品使其安全。

他可以进行的修改只有两种：

• 在发光柱 $k$ 上添加一个发光立方体，即 $S_k\gets S_k+1$。
• 从还有至少一个发光立方体的发光柱 $k$ 上移除一个发光立方体，即 $S_k\gets S_k-1$。

注意，即使一个发光柱没有发光立方体，我们也认为它依然存在于原来的位置。

你的任务是帮助 Squeaky 确定至少需要多少次修改他的作品才能安全。

输入格式

第一行包含两个整数 $N,H$，含义如题所述。

接下来一行 $N$ 个整数，第 $i$ 个表示 $S_i$，即发光柱 $i$ 的初始高度。

输出格式

一行一个整数，Squeaky 为了使他的作品安全需要的最少修改次数。

6 1
2 10 0 2 4 3

10

6 3
2 10 2 6 4 3

6

4 1
1 4 1 4

4

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

0

3 0
1 1 3

2

提示

样例 #1 解释

如图所示，我们删去红色立方体，添加黄色立方体，通过修改 $10$ 次使 Squeaky 的作品安全：任意相邻的两个发光柱高度差都不超过 $H=1$。

可以证明，不存在少于 $10$ 步的修改方法。

这组样例满足子任务 $3$ 和子任务 $5$ 至 $9$。

样例 #2 解释

如图所示，我们删去红色立方体，添加黄色立方体，通过修改 $6$ 次使 Squeaky 的作品安全。可以证明，不存在少于 $6$ 步的修改方法。

这组样例满足子任务 $5$ 至 $9$。

样例 #3 解释

如图所示，我们删去红色立方体，添加黄色立方体，通过修改 $4$ 次使 Squeaky 的作品安全。可以证明，不存在少于 $4$ 步的修改方法。

这组样例满足子任务 $1$ 至 $3$ 和子任务 $5$ 至 $9$。

样例 #4 解释

Squeaky 的作品本来就是安全的，所以不需要进行修改。

这组样例满足子任务 $3$ 和子任务 $5$ 至 $9$。

样例 #5 解释

如图所示，我们删去红色立方体，通过修改 $2$ 次使 Squeaky 的作品安全。可以证明，不存在少于 $2$ 步的修改方法。

这组样例满足所有子任务。

子任务

对于 $100\%$ 的数据，$1\le N\le 2\times 10^5$，$0\le H\le 10^9$，$0\le S_i\le 10^9$。

子任务	得分	数据范围及特殊性质
$1$	$3$	$N\le 10$，$S_i\le 4$
$2$	$4$	$N\le 14$，$H\le 1$，$S_i\le 4$
$3$	$9$	$N\le10$，$H\le 2$
$4$	$5$	$H=0$
$5$	$6$	$N\le 500$，$S_i\le 400$
$6$	$11$	$N\le 500$，$S_i\le 5\times 10^3$
$7$		$N\le 5\times 10^3$，$S_i\le 5\times 10^3$
$8$	$22$	$N\le 5\times 10^3$
$9$	$29$	无特殊限制