Ввиду тесноты на Бродвее, некоторые из бродвейских театров хотят переехать на соседнюю улицу. Эта улица тоже прямая, но в отличие от предыдущей задачи, расстояния между домами могут быть произвольными.
Для уменьшения конкуренции театры хотят разместиться в домах на этой улице так, чтобы минимальное расстояние между двумя соседними театрами было как можно больше.
Входные данные
Первая строка входных данных содержит количество домов на улице N и количество театров K (1 ≤ K ≤ N ≤ 104). Далее идет N чисел в порядке возрастания – координаты домов на улице.
Выходные данные
Выведите единственное число – наибольшее возможное допустимое расстояние между театрами.