Петя и Вася устроились работать курьерами. В течение очередного рабочего дня им нужно доставить пакеты в n различных точек на прямой. Согласно внутренним правилам компании, доставка пакетов должна быть произведена строго в определённом порядке. Исходно Петя находится в точке с координатой s1, Вася находится в точке с координатой s2, а клиенты находятся в точках x1, x2, ..., xn в порядке требуемого посещения.
Ребята заранее договариваются, кто из них доставит пакет для какого из клиентов, после чего они действуют следующим образом. Когда пакет для i-го клиента доставлен, тот из ребят, кто доставляет пакет для (i + 1)-го клиента, отправляется в путь (это может быть как тот же из них, кто только что приехал в точку xi, так и другой). Тот из друзей, который не занят в доставке текущего пакета, стоит на месте.
Для связи друг с другом ребятам выдали рации. Рации довольно плохо работают на больших расстояниях, поэтому Петя и Вася хотят распределить заказы так, чтобы максимальное расстояние между ними в течение дня было как можно меньше. Помогите Пете и Васе минимизировать максимальное расстояние между ними, соблюдая все правила доставки.
Выходные данные
Выведите единственное целое число — минимальное возможное максимальное расстояние между ребятами в процессе доставки.
Примечание
В первом примере изначальное расстояние между курьерами равно 10. Эта величина и будет ответом, например, Петя может выполнить обе доставки, а Вася останется в начальной точке.
Во втором примере оптимально можно действовать, например, так: Вася доставляет пакет первому клиенту, Петя — второму и, наконец, Вася выполняет доставку пакета третьему клиенту. При таком порядке доставки расстояние между курьерами никогда не превзойдет 1.
В третьем примере есть только два возможных варианта: если доставку единственного пакета осуществляет Петя, то максимальное расстояние между ними будет 5 - 2 = 3. Если же пакет повезёт Вася, то максимальное расстояние составит 4 - 2 = 2. Последний способ является оптимальным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 0 10
5 6
|
10
|
|
2
|
3 2 1
3 4 5
|
1
|
|
3
|
1 4 5
2
|
2
|