Задача №113720. Курьерский клуб
Петя и Вася устроились работать курьерами. В течение очередного рабочего дня им нужно доставить пакеты в n различных точек на прямой. Согласно внутренним правилам компании, доставка пакетов должна быть произведена строго в определённом порядке. Исходно Петя находится в точке с координатой s 1 , Вася находится в точке с координатой s 2 , а клиенты находятся в точках x 1 , x 2 , ..., x n в порядке требуемого посещения.
Ребята заранее договариваются, кто из них доставит пакет для какого из клиентов, после чего они действуют следующим образом. Когда пакет для i -го клиента доставлен, тот из ребят, кто доставляет пакет для ( i + 1) -го клиента, отправляется в путь (это может быть как тот же из них, кто только что приехал в точку x i , так и другой). Тот из друзей, который не занят в доставке текущего пакета, стоит на месте.
Для связи друг с другом ребятам выдали рации. Рации довольно плохо работают на больших расстояниях, поэтому Петя и Вася хотят распределить заказы так, чтобы максимальное расстояние между ними в течение дня было как можно меньше. Помогите Пете и Васе минимизировать максимальное расстояние между ними, соблюдая все правила доставки.
В первой строке даны три целых числа n , s 1 , s 2 ( 1 ≤ n ≤ 100 000 , 0 ≤ s 1 , s 2 ≤ 10 9 ) — количество точек доставки и начальные положения Пети и Васи.
Во второй строке расположены n целых чисел x 1 , x 2 , ..., x n — координаты клиентов ( 0 ≤ x i ≤ 10 9 ), указанные в том порядке, в котором следует выполнять доставку.
Гарантируется, что среди чисел s 1 , s 2 , x 1 , ..., x n нет двух одинаковых.
Выведите единственное целое число — минимальное возможное максимальное расстояние между ребятами в процессе доставки.
В первом примере изначальное расстояние между курьерами равно 10 . Эта величина и будет ответом, например, Петя может выполнить обе доставки, а Вася останется в начальной точке.
Во втором примере оптимально можно действовать, например, так: Петя доставляет пакет первому клиенту, Вася — второму и, наконец, Петя выполняет доставку пакета третьему клиенту. При таком порядке доставки расстояние между курьерами никогда не превзойдет 1 .
В третьем примере есть только два возможных варианта: если доставку единственного пакета осуществляет Петя, то максимальное расстояние между ними будет 5 - 2 = 3 . Если же пакет повезёт Вася, то максимальное расстояние составит 4 - 2 = 2 . Последний способ является оптимальным.
2 0 10 5 6
10
3 2 1 3 4 5
1
1 4 5 2
2