CF875E.Delivery Club

Petya and Vasya got employed as couriers. During the working day they are to deliver packages to n different points on the line. According to the company's internal rules, the delivery of packages must be carried out strictly in a certain order. Initially, Petya is at the point with the coordinate _s_1, Vasya is at the point with the coordinate _s_2, and the clients are at the points _x_1, _x_2, ..., x__n in the order of the required visit.

The guys agree in advance who of them will deliver the package to which of the customers, and then they act as follows. When the package for the i-th client is delivered, the one who delivers the package to the (i + 1)-st client is sent to the path (it can be the same person who went to the point x__i, or the other). The friend who is not busy in delivering the current package, is standing still.

To communicate with each other, the guys have got walkie-talkies. The walkie-talkies work rather poorly at great distances, so Petya and Vasya want to distribute the orders so that the maximum distance between them during the day is as low as possible. Help Petya and Vasya to minimize the maximum distance between them, observing all delivery rules.

佩佳和瓦夏受雇成为快递员。在工作日中，他们需要将包裹递送到一条直线上的 $n$ 个不同地点。根据公司内部规定，包裹的递送必须严格按特定顺序进行。初始时，佩佳位于坐标为 $s_1$ 的位置，瓦夏位于坐标为 $s_2$ 的位置，而客户分别位于 $x_1,\,x_2,\,\dots,\,x_n$（按需访问的顺序排列）。

两人事先约定好各自负责为哪些客户递送包裹，之后按如下方式行动：当第 $i$ 位客户的包裹被送达后，负责向第 $(i+1)$ 位客户递送包裹的人即刻出发前往该客户所在地（此人可以是刚刚完成第 $i$ 次递送的同一人，也可以是另一个人）；而此时未承担当前递送任务的那位朋友则原地静止不动。

为彼此联络，他们配备了对讲机。但由于对讲机在远距离下信号很差，佩佳和瓦夏希望合理分配递送任务，使得一整天中两人之间的最大距离尽可能小。请帮助佩佳和瓦夏在满足所有递送规则的前提下，最小化他们之间可能出现的最大距离。

The first line contains three integers n, _s_1, _s_2 (1 ≤ n ≤ 100 000, 0 ≤ _s_1, _s_2 ≤ 109) — number of points of delivery and starting positions of Petya and Vasya.

The second line contains n integers _x_1, _x_2, ..., x__n — customers coordinates (0 ≤ x__i ≤ 109), in the order to make a delivery.

It is guaranteed, that among the numbers _s_1, _s_2, _x_1, ..., x__n there are no two equal.

第一行包含三个整数 $n$、$s_1$、$s_2$（$1 \leq n \leq 100\,000$，$0 \leq s_1, s_2 \leq 10^9$）—— 分别表示配送点的数量，以及 Petya 和 Vasya 的起始位置。

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$ —— 各顾客的坐标（$0 \leq x_i \leq 10^9$），按需配送的顺序给出。

保证在数字 $s_1, s_2, x_1, \ldots, x_n$ 中不存在两个相等的数。

Output the only integer, minimum possible maximal distance between couriers during delivery.

输出唯一的整数，即配送过程中快递员之间可能的最大距离的最小值。

In the first test case the initial distance between the couriers is 10. This value will be the answer, for example, Petya can perform both deliveries, and Vasya will remain at the starting point.

In the second test case you can optimally act, for example, like this: Vasya delivers the package to the first customer, Petya to the second and, finally, Vasya delivers the package to the third client. With this order of delivery, the distance between the couriers will never exceed 1.

In the third test case only two variants are possible: if the delivery of a single package is carried out by Petya, the maximum distance between them will be 5 - 2 = 3. If Vasya will deliver the package, the maximum distance is 4 - 2 = 2. The latter method is optimal.

在第一个测试用例中，快递员初始距离为 $10$。该值即为答案，例如，Petya 可以完成全部两次配送，而 Vasya 保持在起点不动。

在第二个测试用例中，一种最优操作方式（例如）如下：Vasya 将包裹送达第一位客户，Petya 送达第二位客户，最后 Vasya 再将包裹送达第三位客户。按此配送顺序，两名快递员之间的距离永远不会超过 $1$。

在第三个测试用例中，仅存在两种可能方案：若由 Petya 单独完成该包裹的配送，则他们之间的最大距离为 $5 - 2 = 3$；若由 Vasya 完成配送，则最大距离为 $4 - 2 = 2$。后一种方案更优。