Dla multizbioru $S=\{x_0,x_1,\ldots,x_{m-1}\}$ o rozmiarze $m$ niech $y_0\ge y_1\ge\cdots\ge y_{m-1}$ będą jego elementami uporządkowanymi malejąco. Jego medianę $\operatorname{Median}(S)$ definiujemy jako $\lceil m/2\rceil$-ty największy element, czyli $\operatorname{Median}(S)=y_{\lceil m/2\rceil-1}$. Uwaga: definicja mediany w tym zadaniu może różnić się od zwykle stosowanej.

Dany jest ciąg $[a_0,a_1,\ldots,a_{n-1}]$ o długości $n$ i dodatnia liczba całkowita $k$ ($k\le n$). Podział definiujemy następująco: wybieramy rosnący ciąg $k-1$ indeksów $0<b_1<\cdots<b_{k-1}<n$, dzieląc pierwotny ciąg na $k$ fragmentów odpowiadających przedziałom indeksów $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$.

Równowagę podziału definiujemy następująco: dla każdego fragmentu obliczamy medianę multizbioru jego elementów, a następnie medianę multizbioru tych $k$ median. Formalnie, dla podziału $b_1,\ldots,b_{k-1}$ przyjmijmy $b_0=0$, $b_k=n$. Niech $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$ będzie medianą elementów fragmentu $i$ ($0\le i<k$). Równowaga podziału wynosi $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$.

Wyznacz największą równowagę spośród wszystkich podziałów.

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji main.

Plik źródłowy rozwiązania musi zawierać nagłówek median.h. Dodaj na początku programu:

#include "median.h"

W pliku źródłowym median.cpp zaimplementuj następujące dwie funkcje:

void init(int c, int t);

• $c,t$ oznaczają odpowiednio numer testu i liczbę zestawów danych. $c=0$ oznacza test przykładowy.
• Dla każdego testu program oceniający wywoła tę funkcję dokładnie raz, na początku działania programu.

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

• $n,k,a$ oznaczają odpowiednio długość ciągu, liczbę fragmentów w podziale i dany ciąg.
• Funkcja powinna zwrócić największą równowagę.
• Dla każdego testu program oceniający wywoła tę funkcję dokładnie $t$ razy.

W katalogu zadania znajduje się przykładowy kod template_median.cpp, z którego możesz skorzystać przy pisaniu własnego rozwiązania.

Testowanie programu

W katalogu zadania możesz skompilować plik wykonywalny poleceniem:

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

Otrzymany plik wykonywalny median:

• Wczytuje ze standardowego wejścia dane w następującym formacie:
  • Pierwszy wiersz zawiera dwie nieujemne liczby całkowite $c,t$.
  • Dalej podane są kolejno zestawy danych. Dla każdego zestawu:
    • Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n,k$.
    • Drugi wiersz zawiera $n$ dodatnich liczb całkowitych $a_0,a_1,\ldots,a_{n-1}$.
• Wypisuje na standardowe wyjście dane w następującym formacie:
  • Dla każdego zestawu wypisuje w osobnym wierszu jedną dodatnią liczbę całkowitą: największą równowagę.

Przykład

Wejście 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

Wyjście 1

9
8

Uwagi

Dla pierwszego zestawu jednym z podziałów o największej równowadze jest $b_1=3,b_2=5,b_3=7$. Dzieli on ciąg na cztery fragmenty $[6,5,1]$, $[9,2]$, $[3,10]$, $[7,4,8]$, których mediany wynoszą odpowiednio $5,9,10,7$. Równowaga tego podziału wynosi więc $\operatorname{Median}(\{5,9,10,7\})=9$.

Dla drugiego zestawu jednym z podziałów o największej równowadze jest $b_1=2,b_2=4,b_3=6,b_4=8$. Dzieli on ciąg na pięć fragmentów $[5,7]$, $[3,10]$, $[8,2]$, $[9,1]$, $[6,4]$, których mediany wynoszą odpowiednio $7,10,8,9,6$. Równowaga tego podziału wynosi więc $\operatorname{Median}(\{7,10,8,9,6\})=8$.

Przykład 2

Zobacz pliki median/median2.in i median/median2.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testu $6$.

Przykład 3

Zobacz pliki median/median3.in i median/median3.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testu $9$.

Przykład 4

Zobacz pliki median/median4.in i median/median4.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testu $14$.

Przykład 5

Zobacz pliki median/median5.in i median/median5.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testów $18\sim20$.

Ograniczenia

Niech $N$ oznacza sumę wartości $n$ ze wszystkich zestawów danych w jednym teście. Dla wszystkich danych:

• $1\le t\le20$.
• $5\le n\le10^6$, $2\le k\le n$, $N\le10^6$.
• Dla każdego $0\le i<n$ zachodzi $1\le a_i\le n$.

Własność szczególna A: dla każdego $0\le i<n$ zachodzi $a_i\le2$.