Для мультимножества $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

Примечание

Для первого набора одно из разбиений с наибольшей сбалансированностью задаётся $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–20.

Ограничения

Пусть $N$ — сумма $n$ по всем наборам данных одного теста. Для всех данных выполняется:

• $1\le t\le 20$.
• $5\le n\le 10^6$, $2\le k\le n$, $N\le 10^6$.
• Для всех $0\le i<n$ выполняется $1\le a_i\le n$.

Особое свойство A: для всех $0\le i<n$ выполняется $a_i\le 2$.