分数: 500 点
问题陈述
我们有一副牌,包括 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