問題文

長さ $N$ の整数列 $A=(A_1, A_2, \dots, A_N)$ が与えられます．この整数列 $A$ に対し，次に示す $4$ 種類の操作をそれぞれ $0$ 回以上の何回でも行うことができます．

• 操作 1：$A$ のすべての要素の値を $1$ 増やす．
• 操作 2：$A$ のすべての要素の値を $1$ 減らす．
• 操作 3：$A$ の要素をひとつ選び，その値を $K$ 増やす．この操作を $1$ 回行うと，不自然さが $1$ 増える．
• 操作 4：$A$ の要素をひとつ選び，その値を $K$ 減らす．この操作を $1$ 回行うと，不自然さが $1$ 増える．

最初，不自然さの値は $0$ です．あなたの目標は，$A$ の最小値を $A_{min}$，$A$ の最大値を $A_{max}$ としたとき，$A_{min} \geq L, A_{max} \leq U$ とすることです．ここで，$U-L \geq K$ です．

操作を行うことにより目標を達成した際の，不自然さの値の最小値を求めてください．なお，制約により目標は必ず達成可能であることが示せます．

制約

• 入力は全て整数である．
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 2 \times 10^5$
• $0 \leq L, U \leq 10^{12}$
• $U - L \geq K$
• $0 \leq A_i \leq 10^{12}$

入力

入力は以下の形式で標準入力から与えられる．

$N$ $K$ $L$ $U$
$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを出力せよ．

サンプル

6 12 7 22
8 12 15 25 15 23

1

6 12 10 28
15 30 15 30 15 30

0

5 200000 141421356 173205080
200000000 223606797 244948974 264575131 282842712

302