Background

土拨鼠凡凡来到了身高之神面前, 祈祷他能长高一些

Description

身高之神给他出了一道题, 凡凡需要计算出正确答案才可以长高1cm

身高之神给凡凡一段长度为$n$的数组$a$, 凡凡可以对数组中的每个数字进行修改, 他可以将数字$a_i$修改为$a_i-k 到a_i+k$.

其中$n, k$都是正整数, 请帮忙计算,经过若干次修改后, 数组中的最大值减去最小值的最小差值为多少?

Format

Input

第1行两个整数$n, k$

第2行$n$个数字, 表示数列$a$

Output

输出一个数字表示答案

Samples

5 5
1 6 3 2 4

0

样例解释

将第 1 个数字加 4 变成 5；

将第 2 个数字减 1 变成 5；

将第 3 个数字加 2 变成 5；

将第 4 个数字加 3 变成 5；

将第 5 个数字加 1 变成 5；

Limitation

对于 100% 的数据，有 $2\leq n\leq 10^5,-10^{18}\leq a_i\leq 10^{18}, 1\leq k\leq 10^{18}$。