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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ n ≤ 10⁶;

1 ≤ p < n;

0 ≤ a_i ≤ 10⁹;

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

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

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

---