Ретельний відбір

Limits: 2 sec., 256 MiB

Я дякую Богу за те, що він не зробив мене комп’ютерним науковцем.

Даніель Джуліус Бернштайн

Степан - дуже поважний професор, який дуже ретельно відбирає собі студентів для написання курсової. Звісно, для допуску до такого поважного професора у ролі наукового керівника треба відповідати певним критеріям.

Замірявши черепи кожного зі здобувачів освіти на потоці, пан Степан записав результати до свого блокноту. Тепер за заданим масивом \(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\), а саме масив \([a_l, a_{l+1}, \ldots, a_r]\) для деяких \(1 \leq l \leq r \leq n\), довжина якого дорівнює \(r - l + 1\).

Цефальним індексом називаємо процентне відношення ширини черепа до його довжини. Оскільки ці числа можуть бути дуже схожі між собою, то в масиві \(a\) будуть їх індекси внаслідок стиснення масиву цефальних індексів.

Стиснення масиву - це результат виклику наступної функції на цьому самому масиві:

void compress(vector<int>& a) {
    map<int, int> M;
    for (int& x : a) {
        M[x];
    }
    int idx = 0;
    for (auto& it : M) {
        it.second = idx++;
    }
    for (int& x : a) {
        x = M[x];
    }  
}

Блоки тестів

Блок 1: 10 балів, кожне \(a_i\) рівне 1 або 2.
Блок 2: 20 балів, \(n \leq 1000\).
Блок 3: 40 балів, \(n \leq 10^4\).
Блок 4: 30 балів, без додаткових обмежень.

Input

У першому рядку задано два цілих числа \(n\) та \(k\) — довжина масиву \(a\) та мінімальна довжина його підвідрізків.

У другому рядку задано \(n\) цiлих чисел \(a_1, a_2, \ldots, a_n\) — числа в масиві цефальних індеків після його стиснення.

Output

В єдиному рядку виведіть одне число \(m\) — максимальну медіану, яку можна отримати серед всіх можливих підвідрізків.

Constraints

\(1 \leq k \leq n \leq 2 \cdot 10^5\)

\(1 \leq a_i \leq n\)

Samples

Input (stdin)	Output (stdout)
5 3 1 2 3 2 1	2

Input (stdin)	Output (stdout)
6 2 1 2 3 4 5 6	5

Notes

У першому прикладі всі можливі підвідрізки: [1..3], [1..4], [1..5], [2..4], [2..5], [3..5], і в кожному з них медіана дорівнює 2. Отже, максимальна можлива медіана — 2.

У другому прикладі median([5..6]) = 5.

Element Type	Created	Who	Problem	Compiler	Result	Time (sec.)	Memory (MiB)	#	Actions

F. Ретельний відбір | Rex IT Fest Div. 2