给定一个整数序列 $a_1, a_2, \dots, a_n$ 和一个正整数 $d$，你需要将该序列限制在一个满足 $0 \le r - l \le d$ 的区间 $[l, r]$ 内，以最大化 $\sum_{i=1}^{n-1} |a_i - a_{i+1}|$，其中 $|x|$ 表示 $x$ 的绝对值。更具体地说，将序列限制在区间 $[l, r]$ 内意味着每个元素变为：

$$ a_i := \begin{cases} l, & a_i < l; \\ a_i, & l \le a_i \le r; \\ r, & a_i > r. \end{cases} $$

其中 $l$ 和 $r$ 是由你在给定约束下决定的任意实数。可以证明，最大和总是一个整数。

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 5\,000$) 和 $d$ ($1 \le d \le 10^9$)，分别表示给定序列的长度和参数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示给定的序列。

输出格式

输出一行，包含一个整数，表示最大和。

样例

输入 1

8 3
3 1 4 1 5 9 2 6

输出 1

15

说明

在样例中，你可以将给定序列限制在区间 $[1, 4]$，使其变为 $[3, 1, 4, 1, 4, 4, 2, 4]$，所得的和为最大值 $15$。