407263: GYM102739 E Саша и зачёт

E. Саша и зачётограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Саша принимает зачет по алгоритмам и любит задавать вопросы вида «что изменится в решении, если...». Это требует от студентов хорошего уровня понимания решения задачи. Саша хочет определить какой уровень понимания задачи взять за критерий зачета. У неё есть данные о понимании каждой задачи тестового студента Васи: для решения каждой задачи $$$i$$$, некоторая величина $$$u_i$$$, численно характеризующую его понимание этого решения (чем эта величина больше, тем лучше он понимает решение). Саша хочет подобрать такое $$$A$$$, что все объяснения уровня $$$u_i \ge A$$$ она примет, а для всех значений $$$u_i < A$$$ — объяснение не зачтет. Объяснять задачи нужно по порядку, начиная с первой. Кроме того, если Саша не принимает $$$k$$$ подряд идущих объяснений студента, то слушать объяснение следующей задачи она не будет. Помогите Саше подобрать такое максимальное $$$A$$$, при котором тестовый студент Вася получит зачет.

Студент получает зачет если смог рассказать решение всех $$$n$$$ задач с учетом всех требований экзаменатора.

Входные данные

В первой строке содержатся целые числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 10^5, \, 1 \le k \le n)$$$ — количество решений задач и количество неудачных объяснений подряд, после которого объяснение следующей задачи невозможно.

Во второй строке содержатся целые числа $$$u_1, u_2, \ldots, u_n$$$ $$$(1 \le u_i \le 10^5, \, i = 1, 2, \ldots, n)$$$ — показатель понимания Василием решений.

Выходные данные

В первой строке выведите целое число — максимальное значение понимания для критерия зачета.

Если Вася сможет сдать зачет при любом сколь угодно большом критерии $$$A$$$, то выведите в качестве ответа $$$100000$$$.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 25 & n, k \le 10, u_i \le 100 & \text { подзадача } & \\ \hline 2 & 20 & n, k \le 1000, u_i \le 100 & \text { подзадача } & 1 \\ \hline 3 & 55 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2 \\ \hline \end{array}$$$$$$

ПримерыВходные данные

10 3
8 2 2 6 1 3 7 2 7 2

Выходные данные

6

Входные данные

2 2
8 10

Выходные данные

100000