← 返回题目列表

AtCoder · arc085_b

D. 绝对值

中文机器翻译题面 查看原题

分数: 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