Задача E. Размещение сенсорных узлов

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Исследователи глубин теперь хотят разместить сенсорные узлы на прямой линии для мониторинга состояния воды и миграции подводных животных. На прямой линии, вдоль которой хотят провести наблюдения, выбраны контрольные точки, и известны их координаты. К сожалению, у исследователей не хватает сенсорных узлов для размещения в каждой контрольной точке. Поэтому нужно написать компьютерную программу, которая позволит установить сенсорные узлы в контрольные точки так, чтобы минимальное расстояние между ними было как можно больше.

Пример 2 входных / выходных данных является тривиальным случаем и должен обрабатываться отдельно.Необходимо вывести координату последней контрольной точки.

Формат входных данных

В первой строке вводятся числа N – количество контрольных точек и K – количество сенсорных узлов. Во второй строке задаются N натуральных чисел в порядке возрастания – координаты контрольных точек на прямой линии (координаты не превосходят 109)

Формат выходных данных

Выведите одно число – наибольшее возможное допустимое расстояние между сенсорными узлами.

Ограничения

2 < N < 10001

1 < = K < N

Примеры тестов

Стандартный вход Стандартный выход
1
6 3
2 5 7 11 15 20
9
2
7 1
1 2 3 4 5 6 7
7

0.086s 0.016s 15