G. Магазины
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп живет в городе, который мы будем считать отрезком координатной прямой. Самая левая точка города расположена в точке $$$0$$$, а самая правая — в точке $$$10^{9}$$$.

В городе есть $$$n$$$ магазинов, расположенных в точках с целочисленными координатами, причем $$$i$$$-й магазин расположен в точке $$$a_i$$$. Гарантируется, что среди $$$n$$$ магазинов есть ровно один магазин в точке $$$0$$$ и ровно один магазин в точке $$$10^{9}$$$, а также гарантируется, что в каждой точке с целочисленными координатами есть не более одного магазина.

Правительство решило построить в городе еще $$$m$$$ магазинов. Строить новый магазин в точке, в которой уже был магазин, запрещено, а также в каждой целочисленной точке может быть построено не более одного нового магазина. Также запрещается строить магазины левее точки $$$0$$$ и правее точки $$$10^{9}$$$.

Перед вами стоит задача выбрать, где построить новые $$$m$$$ магазинов таким образом, чтобы среди всех $$$(n+m-1)$$$ пар соседних магазинов максимальное расстояние между магазинами из пары было минимально возможно. Иными словами, мы хотим минимизировать максимальную длину отрезка между двумя соседними магазинами.

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

В первой строке следуют два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le m \le 200\,000$$$) — количество магазинов, которые построены в городе, и количество новых магазинов, которые нужно построить.

Во второй строке следует последовательность различных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно координате $$$i$$$-го уже построенного магазина.

Дополнительное ограничение на входные данные:

  • в заданной последовательности есть ровно одно число $$$0$$$ (магазин в точке с координатой $$$0$$$) и ровно одно число $$$10^{9}$$$ (магазин в точке с координатой $$$10^{9}$$$).
Выходные данные

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

Примеры
Входные данные
4 1
750000000 250000000 0 1000000000
Выходные данные
250000000
Входные данные
2 2
0 1000000000
Выходные данные
333333334
Входные данные
3 17
500000000 0 1000000000
Выходные данные
55555556
Входные данные
4 2000
333333333 0 777777777 1000000000
Выходные данные
499376
Примечание

В первом примере нужно построить новый магазин в точке $$$500\,000\,000$$$. Тогда расстояние между всеми парами соседних магазинов будет равно $$$250\,000\,000$$$.

Во втором примере можно построить два новых магазина в точках $$$333\,333\,333$$$ и $$$666\,666\,666$$$. Тогда магазины будут расположены в точках $$$[0, 333\,333\,333, 666\,666\,666, 1\,000\,000\,000]$$$, а максимальное расстояние между парой соседних будет равно $$$1\,000\,000\,000 - 666\,666\,666 = 333\,333\,334$$$ (между третьим и четвертым магазинами).