圓上放置了 $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