Рассмотрим дорогу, которую можно представить в виде числовой прямой. Вы находитесь в точке \(0\) числовой прямой и хотите добраться из точки \(0\) в точку \(x\) и обратно в точку \(0\).
Вы путешествуете на автомобиле, который расходует \(1\) литр бензина за \(1\) единицу пройденного расстояния. Когда вы стартуете из точки \(0\), ваш автомобиль полностью заправлен (в его бензобаке находится максимально возможное количество топлива).
Вдоль дороги есть \(n\) заправочных станций, расположенных в точках \(a_1, a_2, \dots, a_n\). Приезжая на заправку, вы полностью заправляете свой автомобиль. Обратите внимание, что вы можете заправляться только на заправочных станциях, а в точках \(0\) и \(x\) заправок нет.
Ваша задача — посчитать минимально возможный объем бензобака автомобиля (в литрах), который позволит вам проехать из точки \(0\) в точку \(x\) и обратно в точку \(0\).
Примечание
В первом наборе входных данных примера, если бензобак автомобиля имеет объем \(4\) литра, то доехать до \(x\) и обратно можно следующим образом:
- доехать до точки \(1\), тогда в бензобаке вашего автомобиля останется \(3\) литра топлива;
- заправиться в точке \(1\), тогда в бензобаке вашего автомобиля останется \(4\) литра топлива;
- доехать до точки \(2\), тогда в бензобаке вашего автомобиля останется \(3\) литра топлива;
- заправиться в точке \(2\), тогда в бензобаке вашего автомобиля останется \(4\) литра топлива;
- доехать до точки \(5\), тогда в бензобаке вашего автомобиля останется \(1\) литр топлива;
- заправиться в точке \(5\), тогда в бензобаке вашего автомобиля останется \(4\) литра топлива;
- доехать до точки \(7\), тогда в бензобаке вашего автомобиля останется \(2\) литра топлива;
- доехать до точки \(5\), тогда в бензобаке вашего автомобиля останется \(0\) литров топлива;
- заправиться в точке \(5\), тогда в бензобаке вашего автомобиля останется \(4\) литра топлива;
- доехать до точки \(2\), тогда в бензобаке вашего автомобиля останется \(1\) литр топлива;
- заправиться в точке \(2\), тогда в бензобаке вашего автомобиля останется \(4\) литра топлива;
- доехать до точки \(1\), тогда в бензобаке вашего автомобиля останется \(3\) литра топлива;
- заправиться в точке \(1\), тогда в бензобаке вашего автомобиля останется \(4\) литра топлива;
- доехать до точки \(0\), тогда в бензобаке вашего автомобиля останется \(3\) литра топлива.