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