题目描述

我们有一副由 $N$ 张卡片组成的牌堆。每张卡片上都写着一个整数，第 $i$ 张卡片从顶部开始依次编号为 $a_i$。

两个人 X 和 Y 将使用这副牌堆玩一个游戏。初始时，X 在手中拿着一张写着 $Z$ 的卡片，而 Y 在手中拿着一张写着 $W$ 的卡片。然后，从 X 开始，他们交替执行以下操作：

• 从牌堆顶部抽取任意数量的卡片。然后，舍弃手中的卡片，并将最后抽取的一张卡片保留下来。注意，至少要抽取一张卡片。

当牌堆中没有更多的卡片时，游戏结束。游戏的得分是两个玩家手中卡片上所写整数的绝对差值。

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$

输出

输出得分的值。

示例输入1

3 100 100
10 1000 100

示例输出1

900

如果 X 先抽两张卡片，Y 抽最后一张卡片，得分将为 $|1000 - 100| = 900$。

示例输入2

3 100 1000
10 100 100

示例输出2

900

如果 X 先抽取所有的卡片，得分将为 $|1000 - 100| = 900$。

示例输入3

5 1 1
1 1 1 1 1

示例输出3

0

示例输入4

1 1 1
1000000000

示例输出4

999999999