円上に $N$ 台のロボットが置かれている。最も北の位置を $0$ とし、円を $M$ 等分（$M \ge N$）して、残りの分点に時計回りに $1$ から $M-1$ まで番号を付ける。これにより円上の位置 $0$ から $M-1$ が定義される（図 1）。ロボットは最初、互いに異なる $N$ 個の位置にある。

円上の二つの位置 $x,y$ の間の距離を $y-x$（$y \ge x$）と定義する。位置 $x_i$ にあるロボット $R_i$ は、自身から反時計回りと時計回りの両方向に一定の範囲 $R>0$ 内の点を監視できる。つまり、$x_i$ から反時計回りに距離 $R$ の位置を $a$、時計回りに距離 $R$ の位置を $b$ とすると、ロボット $R_i$ は円上の $a$ から $b$ までの時計回りの部分を監視できる。

円全体を監視したい。最初の配置では監視できない部分があるかもしれないので、その場合はロボットを動かして円全体を監視できるようにしたい。$M \le 2RN$ を仮定することで、円全体を監視できる移動が常に存在する。

ロボットは上で定義した円上の位置にしか移動できず、各ロボットは高々一度だけ移動できる。このとき、ロボットの移動距離の最大値を最小化したい。

例えば下の図 1 では、三台のロボット $R_1,R_2,R_3$ はそれぞれ位置 $1,2,5$ にあり、監視範囲は $R=2$ である。円全体を監視するために、ロボット $R_1$ は位置 $0$ に、ロボット $R_3$ は位置 $6$ に移動する。これは移動距離の最大値を最小にする移動である。

図 1

$N$ 台のロボットの位置、範囲 $R$、整数 $M$ が与えられたとき、円全体を監視できるように移動する際の最大移動距離の最小値を求めて出力せよ。

入力

標準入力から次の情報が与えられる。最初の行にはロボットの台数 $N$（$1 \le N \le 1,000,000$）が与えられる。二行目には監視範囲と円上の位置を定義する二つの整数 $R,M$（$1 \le R,M \le 10^9$、$N \le M \le 2RN$）が与えられる。次の行にはロボットの初期位置を表す互いに異なる $N$ 個の整数 $x_i$（$0 \le x_i \le M-1$、$i=1,\ldots,N$）が空白区切りで与えられる。

小課題

• 小課題 1：全 100 点中 10 点。$M \le 10$。

• 小課題 2：全 100 点中 30 点。$N \le 7,000$。

• 小課題 3：全 100 点中 60 点。元の制約以外に制約はない。

出力

円全体を監視できるようにするロボットの最大移動距離の最小値を標準出力に出力せよ。

入出力例

入力 1

3
2 10
1 2 5

出力 1

1

入力 2

6
1 11
0 1 2 3 4 5

出力 2

2