Para un multiconjunto $S=\{x_0,x_1,\ldots,x_{m-1}\}$ de tamaño $m$, supongamos que, al ordenar todos sus elementos de mayor a menor, obtenemos $y_0\ge y_1\ge\cdots\ge y_{m-1}$. Definimos su mediana $\operatorname{Median}(S)$ como el elemento que ocupa la posición $\lceil m/2\rceil$ entre los mayores, es decir, $\operatorname{Median}(S)=y_{\lceil m/2\rceil-1}$. Atención: la definición de mediana de este problema puede diferir de la habitual.

Se da una secuencia $[a_0,a_1,\ldots,a_{n-1}]$ de longitud $n$ y un entero positivo $k$ ($k\le n$). Una partición se define eligiendo una secuencia creciente de $k-1$ índices $0<b_1<\cdots<b_{k-1}<n$. Así se divide la secuencia original en $k$ segmentos, cuyos intervalos de índices son, respectivamente, $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$.

Definimos el equilibrio de una partición de la siguiente manera: para cada segmento, calculamos la mediana del multiconjunto formado por sus elementos; la mediana del multiconjunto formado por esas $k$ medianas es el equilibrio de la partición. Formalmente, para una partición $b_1,\ldots,b_{k-1}$, sea $b_0=0$, $b_k=n$, y sea $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$ la mediana de todos los elementos del segmento $i$ ($0\le i<k$). El equilibrio de la partición es $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$.

Calcula el máximo equilibrio entre todas las particiones.

Detalles de implementación

No necesitas ni debes implementar la función main.

Debes asegurarte de que el archivo fuente que entregues incluya la cabecera median.h, añadiendo el siguiente código al principio del programa:

#include "median.h"

Debes implementar las siguientes dos funciones en el archivo fuente median.cpp que entregues:

void init(int c, int t);

• $c,t$ indican, respectivamente, el número del caso de prueba y el número de conjuntos de datos. $c=0$ indica que el caso de prueba es un ejemplo.
• Para cada caso de prueba, el evaluador llama a esta función exactamente una vez al comenzar la ejecución del programa.

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

• $n,k,a$ representan, respectivamente, la longitud de la secuencia, el número de segmentos de la partición y la secuencia dada.
• La función debe devolver el máximo equilibrio.
• Para cada caso de prueba, el evaluador llama a esta función exactamente $t$ veces.

El archivo template_median.cpp del directorio del problema contiene código de ejemplo que puedes consultar para implementar tu propio código.

Cómo probar el programa

Puedes compilar un ejecutable en el directorio del problema mediante el siguiente comando:

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

Para el ejecutable median obtenido:

• El ejecutable lee de la entrada estándar los datos con el siguiente formato:

  • La primera línea contiene dos enteros no negativos $c,t$.

  • A continuación se dan los conjuntos de datos en orden. Para cada conjunto:

    • La primera línea contiene dos enteros positivos $n,k$.
    • La segunda línea contiene $n$ enteros positivos $a_0,a_1,\ldots,a_{n-1}$.

• El ejecutable escribe en la salida estándar los datos con el siguiente formato:

  • Para cada conjunto de datos, imprime una línea con un entero positivo: el máximo equilibrio.

Ejemplos

Entrada 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

Salida 1

9
8

Nota

Para el primer conjunto de datos, una partición de equilibrio máximo es $b_1=3$, $b_2=5$, $b_3=7$. Divide la secuencia original en 4 segmentos: $[6,5,1]$, $[9,2]$, $[3,10]$, $[7,4,8]$. Sus medianas son, respectivamente, $5,9,10,7$, por lo que el equilibrio de la partición es $\operatorname{Median}(\{5,9,10,7\})=9$.

Para el segundo conjunto de datos, una partición de equilibrio máximo es $b_1=2$, $b_2=4$, $b_3=6$, $b_4=8$. Divide la secuencia original en 5 segmentos: $[5,7]$, $[3,10]$, $[8,2]$, $[9,1]$, $[6,4]$. Sus medianas son, respectivamente, $7,10,8,9,6$, por lo que el equilibrio de la partición es $\operatorname{Median}(\{7,10,8,9,6\})=8$.

Ejemplo 2

Consulta los archivos median/median2.in y median/median2.ans del directorio del concursante.

Este ejemplo satisface las restricciones del caso de prueba $6$.

Ejemplo 3

Consulta los archivos median/median3.in y median/median3.ans del directorio del concursante.

Este ejemplo satisface las restricciones del caso de prueba $9$.

Ejemplo 4

Consulta los archivos median/median4.in y median/median4.ans del directorio del concursante.

Este ejemplo satisface las restricciones del caso de prueba $14$.

Ejemplo 5

Consulta los archivos median/median5.in y median/median5.ans del directorio del concursante.

Este ejemplo satisface las restricciones de los casos de prueba $18\sim 20$.

Restricciones

Sea $N$ la suma de los valores de $n$ de todos los conjuntos de datos de un caso de prueba. Para todos los conjuntos de datos se cumple:

• $1\le t\le 20$.
• $5\le n\le 10^6$, $2\le k\le n$, $N\le 10^6$.
• Para todo $0\le i<n$, se cumple $1\le a_i\le n$.

Propiedad especial A: para todo $0\le i<n$, se cumple $a_i\le 2$.