Задана полоска, разделенная на клетки, клетки пронумерованы слева направо от \(0\) до \(10^{18}\). Изначально все клетки белые.
Вы можете выполнять следующее действие: выбрать две белые клетки \(i\) и \(j\), такие что \(i \ne j\) и \(|i - j| \le k\), и покрасить их в черный цвет.
Задан список \(a\). Все клетки из этого списка должны быть покрашены в чёрный. Также в черный цвет может быть покрашено не более одной клетки, не входящей в этот список. Ваша задача — определить, для какого минимального значения \(k\) это возможно.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное значение \(k\), для которого возможно покрасить все заданные клетки.
Примечание
В первом наборе входных данных с параметром \(k=1\) можно покрасить клетки \((1, 2)\).
Во втором наборе входных данных с параметром \(k=1\) можно покрасить клетки \((7, 8)\).
В третьем наборе входных данных с параметром \(k=2\) можно покрасить клетки \((2, 4)\) и \((8, 9)\).
В четвертом наборе входных данных с параметром \(k=3\) можно покрасить клетки \((0, 1)\), \((5, 8)\) и \((10, 13)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13
|
1
1
2
3
|