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。后一种方法是最佳方法。