Задача G3. Горячий кофе

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Известно, что наличие кофемашины — это очень важный для программистов фактор при выборе места работы. В одной программистской конторе нужны новые сотрудники, и шеф решил в первую очередь выбирать новую кофемашину, надеясь повысить привлекательность конторы. Поскольку шеф сам программировал когда-то, ему не составило труда разработать математическую модель того, как программисты пьют кофе.

Каждый программист, придя утром на работу, первым делом идёт на кухню к кофемашине. Если машина свободна, то программист включает её, и она делает кофе в течение t единиц времени. Как только кофе готов, программист забирает его и уходит пить на рабочем месте. Временем выхода программиста из кухни можно пренебречь. Если же машина занята, то программист понимает, что имеет дело с очередью, и занимает место в её конце, разговаривая с коллегами из очереди о работе.

Шеф знает, что разговоры в очереди к кофемашине плодотворно влияют на дальнейшую производительность программистов в течение всего дня. Поэтому, имеет смысл выбирать кофемашину с наибольшим параметром t. Но если количество программистов в очереди превысит константу p, то программисты перестанут уходить из очереди с готовым кофе и разговор затянется.

Зная момент времени, в который каждый программист приходит на работу, помогите выбрать шефу наибольший целочисленный параметр t, который не приведёт к очереди длиннее p.

Если один программист заходит на кухню, а другой в этот же момент времени выходит, то считается что они не стоят в одной очереди.

Формат входного файла

В первой строке входного файла содержится два целых числа — n и p. Во второй строке записаны n целых чисел a1, a2, , an, задающих время прихода каждого программиста на работу (время считается от начала рабочего дня в тех же единицах, в которых необходимо выдать ответ).

Формат выходного файла

В выходной файл выведите единственное число — ответ к задаче.

Ограничения

2 ≤ n ≤ 106;

1 ≤ p < n;

0 ≤ ai ≤ 109;

Все ai различны.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
0 30 10 
30

0.103s 0.017s 15