题目描述

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

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

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

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

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

输入格式

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

$N$ $Z$ $W$ $a_1$ $a_2$ $...$ $a_N$

输出格式

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

题目大意

有一堆 $N$ 张牌，每张牌上有一个数，从上到下第 $i$ 牌上面的数为 $a_i$。

两个人 X,Y 用这堆牌玩游戏。一开始，X,Y 手上分别有一张牌，上面的数分别为 $Z,W$，接下来，从 X 开始，两个人会轮流进行如下操作直到牌堆为空：

• 拿出牌堆最上方的若干张牌（至少一张），移除自己手上的牌，保留拿出的最后一张牌。

牌堆为空后，这局游戏的得分为 X,Y 手上的牌上的数的差的绝对值。

X 会让最终得分尽可能大，Y 会让最终得分尽可能小。那么，两人按照这样的方式游玩时，最终得分会是多少？

3 100 100
10 1000 100

900

3 100 1000
10 100 100

900

5 1 1
1 1 1 1 1

0

1 1 1
1000000000

999999999

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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