配点 : $500$ 点

問題文

$N$ 枚のカードからなる山札があります。カードにはそれぞれ数が書かれており， 上から $i$ 枚目には $a_i$ が書かれています。

この山札を使い，X さんと Y さんが $2$ 人でゲームをします。 X, Y さんは最初，$Z, W$ が書かれたカードを持っています。 そして X さんから交互に以下を行います。

• 山札から何枚かカードを引く。そして今持っているカードを捨て，最後に引いたカードを代わりに持つ。ただし，必ず $1$ 枚は引かなくてはならない。

山札がなくなるとゲームは終了で，$2$ 人の持っているカードに書かれた数の差の絶対値がこのゲームのスコアになります。

X さんはスコアを最大化するように，Y さんはスコアを最小化するようにゲームをプレイした時， スコアはいくつになるでしょうか？

制約

• 入力は全て整数
• $1 \leq N \leq 2000$
• $1 \leq Z, W, a_i \leq 10^9$

入力

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

$N$ $Z$ $W$

$a_1$ $a_2$ $...$ $a_N$

出力

求めたスコアを出力してください。

3 100 100
10 1000 100

900

X さんが最初に $2$ 枚カードを引くと，次に Y さんが最後のカードを引き，スコアは $|1000 - 100| = 900$ になります。

3 100 1000
10 100 100

900

X さんが最初に全てのカードを引くと，スコアは $|100 - 1000| = 900$ になります。

5 1 1
1 1 1 1 1

0

1 1 1
1000000000

999999999