Монокарп живет в городе, который мы будем считать отрезком координатной прямой. Самая левая точка города расположена в точке $$$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$$$-го уже построенного магазина.
Дополнительное ограничение на входные данные:
Выведите одно целое число — минимально возможное максимальное расстояние между двумя соседними магазинами.
4 1750000000 250000000 0 1000000000
250000000
2 20 1000000000
333333334
3 17500000000 0 1000000000
55555556
4 2000333333333 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$$$ (между третьим и четвертым магазинами).
