题目描述

有一副由 $N$ 张牌组成的牌堆。每张牌上都写有一个数字，第 $i$ 张牌上写有 $a_i$。

现在 X 和 Y 两个人利用这副牌玩游戏。X 和 Y 一开始分别持有写有 $Z$、$W$ 的牌。接着，从 X 开始，两人轮流进行如下操作：

• 从牌堆中抽取若干张牌。然后将手里的牌弃置，拿所抽取的最后一张牌作为手牌。需要注意的是，至少要抽取一张牌。

当牌堆中的牌被抽完后，游戏结束。两人此时所持有手牌上的数字之差的绝对值，就是本局游戏的得分。

X 会以使分数最大为目标，Y 则以使分数最小为目标进行游戏。请问，最终分数会是多少？

输入格式

输入以以下格式从标准输入给出。

$N$ $Z$ $W$ $a_1$ $a_2$ $\cdots$ $a_N$

输出格式

请输出所求的分数。

样例 1

输入

3 100 100
10 1000 100

输出

900

样例 2

输入

3 100 1000
10 100 100

输出

900

样例 3

输入

5 1 1
1 1 1 1 1

输出

0

样例 4

输入

1 1 1
1000000000

输出

999999999

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2000$
• $1 \leq Z,\ W,a_i \leq 10^9$

样例解释1

如果 X 一开始抽取第 2 张牌，接着 Y 抽取最后一张牌，则分数为 $|1000-100|=900$。

样例解释2

如果 X 一开始抽取所有的牌，则分数为 $|100-1000|=900$。

由 ChatGPT 5 翻译