Злі корови (Срібло)
Бессі створила нову гру. Гравець стріляє коровами на одномірну сцену, що складається з багатьох стогів сіна, розташованих у різних точках на числовій прямій. Кожна корова приземляється з силою, достатньою, щоб зруйнувати найближчі до точки приземлення стоги. Мета - використати корів так, щоб зруйнувати всі стоги сіна.
Є 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, з якою повинна приземлитися кожна корова, щоб зруйнувати всі стоги сіна.