D. Максимальная медиана
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ длины $$$n$$$. Найдите такой подмассив $$$a[l..r]$$$ длиной хотя бы $$$k$$$, что у него максимально возможная медиана.

Медианой в массиве длины $$$n$$$ называется элемент, стоящий на позиции $$$\lfloor \frac{n + 1}{2} \rfloor$$$ после сортировки всех элементов в неубывающем порядке. Например: $$$median([1, 2, 3, 4]) = 2$$$, $$$median([3, 2, 1]) = 2$$$, $$$median([2, 1, 2, 1]) = 1$$$.

Подмассив $$$a[l..r]$$$ — это последовательная часть массива $$$a$$$, то есть массив $$$a_l,a_{l+1},\ldots,a_r$$$ для каких-то $$$1 \leq l \leq r \leq n$$$, он имеет длину $$$r - l + 1$$$.

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

В первой строке находятся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$).

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

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

Выведите одно целое число $$$m$$$ — максимальную медиану, которую можно получить.

Примеры
Входные данные
5 3
1 2 3 2 1
Выходные данные
2
Входные данные
4 2
1 2 3 4
Выходные данные
3
Примечание

В первом примере все возможные массивы: $$$[1..3]$$$, $$$[1..4]$$$, $$$[1..5]$$$, $$$[2..4]$$$, $$$[2..5]$$$ и $$$[3..5]$$$, и во всех них медиана равна $$$2$$$, соответственно, максимальная медиана также равна $$$2$$$.

Во втором примере $$$median([3..4]) = 3$$$.