← 返回题目列表

Codeforces · 875/E

E. 送货俱乐部

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

Petya 和 Vasya 受聘担任快递员。在工作日期间,他们将包裹运送到生产线上的 n 个不同地点。根据公司内部规定,包裹的投递必须严格按照一定的顺序进行。最初,Petya 位于坐标 s1 的点,Vasya 位于坐标 s2 的点,客户端按所需访问的顺序位于点 x1、x2、...、xn。

这些人提前同意谁将包裹交付给哪个客户,然后他们按照以下方式行事。当第 i 个客户端的包裹被递送时,将包裹递送给第 (i + 1) 个客户端的人被发送到该路径(可以是到达点 xi 的同一个人,也可以是另一个)。不忙着递送当前包裹的朋友站在原地。

为了互相交流,这些人都有对讲机。对讲机在远距离上的工作效果相当差,因此 Petya 和 Vasya 希望分配命令,以便白天之间的最大距离尽可能短。帮助 Petya 和 Vasya 最小化他们之间的最大距离,遵守所有交付规则。

输入

第一行包含三个整数 n、s1、s2 (1 ≤ n ≤ 100 000, 0 ≤ s1, s2 ≤ 109) — Petya 和 Vasya 的投递点数量和起始位置。

第二行包含 n 个整数 x1, x2, ..., xn — 客户坐标 (0 ≤ xi ≤ 109),按照发货顺序。

保证在数字 s1、s2、x1、...、xn 中没有两个相等。

输出

输出唯一的整数,投递过程中快递员之间的最小可能最大距离。

示例

输入 #1

2 0 10
5 6

输出 #1

10

输入 #2

3 2 1
3 4 5

输出 #2

1

输入 #3

1 4 5
2

输出 #3

2

注意

在第一个测试用例中,快递员之间的初始距离为 10。该值将是答案,例如,Petya 可以执行两次送货,而 Vasya 将保留在起点。

在第二个测试用例中,您可以采取最佳行动,例如,如下所示:Vasya 将包裹交付给第一个客户,Petya 交付给第二个客户,最后,Vasya 将包裹交付给第三个客户。按照这样的配送顺序,快递员之间的距离永远不会超过1。

在第三个测试用例中,只有两种可能的变体:如果 Petya 交付单个包裹,则它们之间的最大距离将为 5 - 2 = 3。如果 Vasya 交付包裹,则最大距离为 4 - 2 = 2。后一种方法是最佳方法。