Для мультимножини $S=\{x_0,x_1,\ldots,x_{m-1}\}$ розміру $m$ нехай її елементи після сортування за спаданням мають вигляд $y_0\ge y_1\ge\cdots\ge y_{m-1}$. Визначимо медіану $Median(S)$ як $\lceil m/2\rceil$-й за величиною елемент, тобто $Median(S)=y_{\lceil m/2\rceil-1}$. Увага: визначення медіани в цій задачі може відрізнятися від звичного.

Задано послідовність $[a_0,a_1,\ldots,a_{n-1}]$ довжини $n$ і додатне ціле число $k$ ($k\le n$). Розбиття визначається вибором зростаючої послідовності $k-1$ індексів $0<b_1<\cdots<b_{k-1}<n$. Вона розбиває початкову послідовність на $k$ відрізків з індексами $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$ відповідно.

Визначимо збалансованість розбиття так: для кожного відрізка обчислимо медіану мультимножини всіх його елементів. Медіана мультимножини цих $k$ медіан і є збалансованістю розбиття. Формально, для розбиття $b_1,\ldots,b_{k-1}$ позначимо $b_0=0$, $b_k=n$. Нехай медіана мультимножини всіх елементів відрізка $i$ ($0\le i<k$) дорівнює $c_i=Median(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$. Тоді збалансованість розбиття дорівнює $Median(\{c_0,\ldots,c_{k-1}\})$.

Знайдіть найбільшу збалансованість серед усіх розбиттів.

Деталі реалізації

Не потрібно й не слід реалізовувати функцію main.

Переконайтеся, що поданий файл програми підключає заголовок median.h, додавши на початку такий код:

#include "median.h"

У файлі median.cpp потрібно реалізувати дві функції:

void init(int c, int t);

• $c,t$ — номер тесту та кількість наборів даних відповідно. Значення $c=0$ означає, що тест є прикладом.
• Для кожного тесту перевіряльна програма викликає цю функцію рівно один раз на початку виконання.

int median(int n, int k, std::vector<int> a);

• $n,k,a$ — довжина послідовності, кількість відрізків розбиття та задана послідовність відповідно.
• Функція має повернути найбільшу збалансованість.
• Для кожного тесту перевіряльна програма викликає цю функцію рівно $t$ разів.

У каталозі задачі надано приклад коду template_median.cpp, яким можна скористатися як зразком для власної реалізації.

Тестування програми

У каталозі задачі можна скомпілювати виконуваний файл командою:

g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static

Для отриманого виконуваного файлу median:

• Програма читає зі стандартного вводу дані в такому форматі:

  • Перший рядок містить два невід'ємні цілі числа $c,t$.

  • Далі послідовно наведено набори даних. Для кожного набору:

    • Перший рядок містить два додатні цілі числа $n,k$.
    • Другий рядок містить $n$ додатних цілих чисел $a_0,a_1,\ldots,a_{n-1}$.

• Програма виводить у стандартний вивід дані в такому форматі:

  • Для кожного набору виводиться один рядок з одним додатним цілим числом — найбільшою збалансованістю.

Приклади

Вхідні дані 1

0 2
10 4
6 5 1 9 2 3 10 7 4 8
10 5
5 7 3 10 8 2 9 1 6 4

Вихідні дані 1

9
8

Пояснення 1

Для першого набору одним із розбиттів із найбільшою збалансованістю є $b_1=3$, $b_2=5$, $b_3=7$. Воно дає 4 відрізки $[6,5,1]$, $[9,2]$, $[3,10]$, $[7,4,8]$. Їхні медіани відповідно дорівнюють $5,9,10,7$, тому збалансованість розбиття дорівнює $Median(\{5,9,10,7\})=9$.

Для другого набору одним із розбиттів із найбільшою збалансованістю є $b_1=2$, $b_2=4$, $b_3=6$, $b_4=8$. Воно дає 5 відрізків $[5,7]$, $[3,10]$, $[8,2]$, $[9,1]$, $[6,4]$. Їхні медіани відповідно дорівнюють $7,10,8,9,6$, тому збалансованість дорівнює $Median(\{7,10,8,9,6\})=8$.

Приклад 2

Дивіться файли median/median2.in і median/median2.ans у каталозі учасника.

Цей приклад задовольняє обмеження тесту 6.

Приклад 3

Дивіться файли median/median3.in і median/median3.ans у каталозі учасника.

Цей приклад задовольняє обмеження тесту 9.

Приклад 4

Дивіться файли median/median4.in і median/median4.ans у каталозі учасника.

Цей приклад задовольняє обмеження тесту 14.

Приклад 5

Дивіться файли median/median5.in і median/median5.ans у каталозі учасника.

Цей приклад задовольняє обмеження тестів $18\sim20$.

Обмеження

Нехай $N$ — сума значень $n$ усіх наборів даних одного тесту. Для всіх наборів:

• $1\le t\le20$.
• $5\le n\le10^6$, $2\le k\le n$, $N\le10^6$.
• Для всіх $0\le i<n$ виконується $1\le a_i\le n$.

Особлива властивість A: для всіх $0\le i<n$ виконується $a_i\le2$.