Злые коровы (Серебро)
Бесси создала новую игру. Игрок стреляет коровами на одномерную сцену, состоящую из множества стогов сена расположенных в различных точках на числовой прямой. Каждая корова приземляется с силой достаточной, чтобы разрушить ближайшие к точке приземления стоги. Цель - использовать множество коров так, чтобы разрушить все стоги сена.
Имеется n стогов сена расположенных в целочисленных позициях x[1], x[2], ... , x[n] на числовой прямой. Если корова приземляется с энергией r в позиции x, это вызывает взрыв "радиуса r", разрушающий все стоги сена в диапазоне x − r ... x + r.
Всего имеется k коров для выстрелов, каждая с одной и той же энергией r. Определите минимальную целую величину r такую, что возможно используя эти k коров разрушить все стоги сена на сцене.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 50000) и k (1 ≤ k ≤ 10). Каждая из оставшихся n строк содержит целые числа x[1] ... x[n] (каждое в интервале 0 ... 10^9).
Выходные данные
Выведите минимальную энергию r, с которой должна приземлиться каждая корова, для того чтобы разрушить все стоги сена.