CF875E Delivery Club

Petya 和 Vasya 成为了快递员。在工作日内，他们需要按照规定的顺序，将包裹送到一条直线上的 $n$ 个不同地点。根据公司的内部规定，快递必须严格按照给定顺序投递。最开始，Petya 站在坐标为 $s_1$ 的点，Vasya 站在坐标为 $s_2$ 的点，客户依次在坐标 $x_1,x_2,\ldots,x_n$。 他们需要事先约定每个包裹由哪一个人送，然后按照以下规则进行：每当第 $i$ 个客户的包裹送达后，去给第 $i+1$ 个客户送包裹的人就可以出发（可以是同一个人也可以换人）。在当前未去送包裹的人，会一直保持在原地不动。 他们各有一台对讲机，然而对讲机距离远了就不好用，所以 Petya 和 Vasya 希望分配任务，使得他们在一天中两人距离的最大值尽可能的小。请帮他们在满足所有快递规则的前提下，最小化他们之间的最大距离。

第一行包含三个整数 $n$、$s_1$、$s_2$，表示快递点数以及 Petya 和 Vasya 的初始位置（$1 \leq n \leq 100\,000$，$0 \leq s_1, s_2 \leq 10^9$）。 第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$，表示客户的坐标，按照要求访问的顺序（$0 \leq x_i \leq 10^9$）。 保证 $s_1, s_2, x_1, ..., x_n$ 都两两不同。

输出一个整数，表示两人投递过程中两者最大距离的最小可能值。

在第一个样例中，两人的初始距离为 $10$。例如 Petya 可以完成所有包裹的投递，而 Vasya 保持不动，则最大距离就是 $10$。 在第二个样例中，可以选择最优分配：比如 Vasya 送第一个包裹，Petya 送第二个包裹，最后 Vasya 再送第三个包裹。采用这种顺序，两人间的最远距离不会超过 $1$。 在第三个样例中，只有两种分配方式：如果 Petya 送包裹，两人最大距离为 $5-2=3$；如果 Vasya 送包裹，最大距离为 $4-2=2$。后者更优。 由 ChatGPT 5 翻译