На прямой исследовательской тропе есть n подходящих мест для установки датчиков. Координаты всех мест известны и различны. Алекс должен поставить ровно k датчиков, не более одного в каждом месте.
Чтобы датчики меньше мешали друг другу, Алекс хочет сделать минимальное расстояние между любыми двумя установленными датчиками как можно больше. Найдите наибольшее возможное значение этого минимального расстояния.
Первая строка содержит целые числа n и k (2 ≤ k ≤ n ≤ 200 000). Вторая строка содержит n различных целых координат xᵢ (0 ≤ xᵢ ≤ 109) в произвольном порядке.
Выведите максимальное минимальное расстояние.
Пример 1. Можно поставить датчики в точках 1, 4 и 8. Минимальное расстояние равно 3.
Пример 2. Нужно занять оба места.
5 3 1 2 8 4 9
3
2 2 1000000000 0
1000000000
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач