山峦起伏

题目背景

盘山公路通车之前，测量队沿着路面每隔固定的距离打下一根木桩，记下每根木桩处路面的海拔高度。

养护段只负责坡度平缓的路段：相邻两根木桩之间的海拔差只要超过 $D$ 米，这里就会被判定为陡坡，不属于他们的责任范围。而在连续平缓的一段路上，工程师需要统计「这段路的最高点与最低点相差多少米」，再把统计出来的所有数字相加，用来估算护栏的总长度。

题目描述

给定长度为 $n$ 的整数序列 $h_1,h_2,\dots,h_n$ 和一个非负整数 $D$。

称区间 $[l,r]$（$1\le l\le r\le n$）是平缓的，当且仅当对每个满足 $l\le i<r$ 的整数 $i$，都有 $|h_{i+1}-h_i|\le D$。

对于每一个平缓区间 $[l,r]$，定义它的起伏度为

$$f(l,r)=\max_{l\le i\le r}h_i-\min_{l\le i\le r}h_i .$$

请你计算所有平缓区间的起伏度之和。长度为 $1$ 的区间一定平缓，其起伏度为 $0$。

输入格式

从标准输入读入数据。

第一行两个整数 $n,D$。

第二行 $n$ 个整数 $h_1,h_2,\dots,h_n$。

输出格式

输出到标准输出。

一行一个整数，表示所有平缓区间的起伏度之和。

样例 1 输入

5 1
3 4 3 9 8

样例 1 输出

4

样例 1 解释

第三根木桩与第四根木桩的海拔差为 $|9-3|=6>1$，这里是一段陡坡，因此平缓区间只能完整地落在 $[1,3]$ 或 $[4,5]$ 之中。

落在 $[1,3]$ 里的平缓区间有 $[1,1],[2,2],[3,3],[1,2],[2,3],[1,3]$，起伏度依次为 $0,0,0,1,1,1$，合计 $3$。

落在 $[4,5]$ 里的平缓区间有 $[4,4],[5,5],[4,5]$，起伏度依次为 $0,0,1$，合计 $1$。

总答案为 $3+1=4$。

样例 2 输入

3 0
5 5 5

样例 2 输出

0

样例 2 解释

取 $D=0$ 时，只有相邻木桩海拔完全相同的位置才算平缓。三根木桩的海拔都是 $5$，整个序列是平缓的，但任意一段区间里最高点与最低点都相等，所以起伏度全部为 $0$。

样例 3 输入

4 10000
1 5 2 9

样例 3 输出

33

样例 3 解释

相邻海拔差最大为 $|9-2|=7$，不超过 $10000$，所以整个序列都是平缓的。全部 $10$ 个区间的起伏度之和为

$$0+0+0+0+4+3+7+4+7+8=33 .$$

数据范围

对于所有测试数据，$1\le n\le 5\times 10^5$，$0\le D\le 10^4$，$1\le h_i\le 10^4$，答案可以使用 $64$ 位有符号整数存下。

测试点编号	$n$	特殊性质
$1\sim 4$	$\le 100$	无
$5\sim 8$	$\le 1000$
$9\sim 12$	$\le 5\times 10^5$	A
$13\sim 16$		B
$17\sim 20$		无

特殊性质 A：$D\ge 10^4$，此时任何区间都是平缓的。

特殊性质 B：$h_1\le h_2\le\dots\le h_n$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。