410223: GYM103985 I Курьерский клуб

I. Курьерский клубограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Петя и Вася устроились работать курьерами. В течение очередного рабочего дня им нужно доставить пакеты в n различных точек на прямой. Согласно внутренним правилам компании, доставка пакетов должна быть произведена строго в определённом порядке. Исходно Петя находится в точке с координатой s₁, Вася находится в точке с координатой s₂, а клиенты находятся в точках x₁, x₂, ..., x_n в порядке требуемого посещения.

Ребята заранее договариваются, кто из них доставит пакет для какого из клиентов, после чего они действуют следующим образом. Когда пакет для i-го клиента доставлен, тот из ребят, кто доставляет пакет для (i + 1)-го клиента, отправляется в путь (это может быть как тот же из них, кто только что приехал в точку x_i, так и другой). Тот из друзей, который не занят в доставке текущего пакета, стоит на месте.

Для связи друг с другом ребятам выдали рации. Рации довольно плохо работают на больших расстояниях, поэтому Петя и Вася хотят распределить заказы так, чтобы максимальное расстояние между ними в течение дня было как можно меньше. Помогите Пете и Васе минимизировать максимальное расстояние между ними, соблюдая все правила доставки.

Входные данные

В первой строке даны три целых числа n, s₁, s₂ (1 ≤ n ≤ 100 000, 0 ≤ s₁, s₂ ≤ 10⁹) — количество точек доставки и начальные положения Пети и Васи.

Во второй строке расположены n целых чисел x₁, x₂, ..., x_n — координаты клиентов (0 ≤ x_i ≤ 10⁹), указанные в том порядке, в котором следует выполнять доставку.

Гарантируется, что среди чисел s₁, s₂, x₁, ..., x_n нет двух одинаковых.

Выходные данные

Выведите единственное целое число — минимальное возможное максимальное расстояние между ребятами в процессе доставки.

ПримерыВходные данные

2 0 10
5 6

Выходные данные

10

Входные данные

3 2 1
3 4 5

Выходные данные

1

Входные данные

1 4 5
2

Выходные данные

2

Примечание

В первом примере изначальное расстояние между курьерами равно 10. Эта величина и будет ответом, например, Петя может выполнить обе доставки, а Вася останется в начальной точке.

Во втором примере оптимально можно действовать, например, так: Петя доставляет пакет первому клиенту, Вася — второму и, наконец, Петя выполняет доставку пакета третьему клиенту. При таком порядке доставки расстояние между курьерами никогда не превзойдет 1.

В третьем примере есть только два возможных варианта: если доставку единственного пакета осуществляет Петя, то максимальное расстояние между ними будет 5 - 2 = 3. Если же пакет повезёт Вася, то максимальное расстояние составит 4 - 2 = 2. Последний способ является оптимальным.