問題文

すぬけ君はすめけさんと二人で数の書かれたカードとコインを使って以下のようなゲームをすることにしました。

はじめ、すぬけ君は $T$ が書かれたカード一枚と $K$ 枚のコインを、すめけさんはカードを $N$ 枚持っている。
このゲームは $N$ 回のラウンドに分かれていて、すめけさんは各ラウンドでは以下の手順を一回行う。

• すめけさんはまだすぬけ君に見せていないカードを一枚選び、それをすぬけ君に見せる。このカードに書かれている数字を $A$ とする。
• すぬけ君の持っているカードに書かれた数字を $B$ とすると、すぬけ君はすめけさんから$|A-B|$ ダメージを受ける。
• すぬけ君はコインを持っているとき、すめけさんにコインを一枚渡して $A$ のカードを $B$ のカードと交換するか、コインを渡さずに何もしないかのどちらかを行う。

このゲームにおいて、すぬけ君は各ラウンドで受けるダメージの最大値を最小化したい。

そこで、すぬけ君はすめけさんの作戦を探り出し、すめけさんはすぬけ君の行動に関わらず $i$ 回目に書かれている値が $A_i$ のカードを出すのだと確信した。

すぬけ君が各ラウンドで受けるダメージの最大値として考えられる最小の値を求めてくさだい。
ただし、各ラウンドが終わった後、すぬけ君のダメージはすめけさんによって回復されることとする。

入力

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

$N$ $T$ $K$ $A_1$ $A_2$ $...$ $A_N$

• 一行目にはラウンドの数 $N(1≦N≦100,000)$とすぬけ君が最初に持っているカードに書かれている数 $T(1≦T≦10^{9})$、コインの枚数 $K(1≦K≦N)$ が与えられる。
• 次の行には$N$ 個の数が与えられ、$i$ 個目の整数としてすめけさんが $i(1≦i≦N)$ 回目に出すカードに書かれている数 $A_{i}(1≦A_{i}≦10^{9})$ が与えられる。

配点

この問題には部分点があります。追加制約として、 $N=K$ を満たす場合についてこの問題を解くと20点が与えられます。

出力

すぬけ君が各ラウンドで受けるダメージの最大値として考えられる最小の値を一行に出力せよ。 末尾には改行を入れること。

入力例$1$

5 1 1
1 2 3 4 5

出力例$1$

2

入力例$2$

8 9 3
11 4 5 14 19 19 8 10

出力例$2$

6