Беси создала новую игру.
Игрок стреляет коровами на одномерную сцену, состоящую из множества стогов сена
расположенных в различных точках на числовой прямой. Каждая корова приземляется
с силой достаточной, чтобы разрушить ближайшие к точке приземления стоги.
Цель - использовать множество коров так, чтобы разрушить все стоги сена.
Имеется \(N\) стогов сена расположенных в целочисленных позициях
\(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземляется с энергией \(R\)
в позиции \(x\), это вызывает взрыв "радиуса \(R\)", разрушающий все стоги
сена в диапазоне \(x-R \ldots x+R\).
Всего имеется \(K\) коров для выстрелов, каждая с одной и той же энергией \(R\).
Определите минимальную целую величину \(R\) такую, что возможно используя эти \(K\)
коров разрушить все стоги сена на сцене.
ФОРМАТ ВВОДА (файл angry.in):
Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)) и \(K\)
(\(1 \leq K \leq 10\)). Каждая из оставшихся \(N\) строк содержит целые числа
\(x_1 \ldots x_N\) (каждое в интервале \(0 \ldots 1,000,000,000\)).
ФОРМАТ ВЫВОДА (файл angry.out):
Выведите минимальную энергию \(R\), с которой должна приземлиться каждая корова,
для того чтобы разрушить все стоги сена.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
20
25
18
8
10
3
1
|
5
|