要素数 $m$ の多重集合 $S=\{x_0,x_1,\ldots,x_{m-1}\}$ の要素を大きい順に並べた結果を、$y_0 \geq y_1 \geq \cdots \geq y_{m-1}$ とします。その中央値 $\operatorname{Median}(S)$ を、$\lceil m/2\rceil$ 番目に大きい数、すなわち $\operatorname{Median}(S)=y_{\lceil m/2\rceil-1}$ と定義します。この問題での中央値の定義は、通常の定義と異なる場合があることに注意してください。

長さ $n$ の列 $[a_0,a_1,\ldots,a_{n-1}]$ と、正整数 $k$（$k \leq 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 \leq i<k$）の区間の中央値を $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$ とすると、平衡度は $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$ です。

すべての分割の中で、平衡度の最大値を求めてください。

実装の詳細

main 関数を実装する必要はなく、実装してはいけません。

提出するソースファイルにはヘッダ median.h を含めてください。すなわち、プログラムの先頭に次のコードを加えてください。

#include "median.h"

提出するソースファイル median.cpp に、次の 2 つの関数を実装してください。

void init(int c, int t);

• $c,t$ は、それぞれテストケース番号とテストデータの個数です。$c=0$ はサンプルを表します。
• 各テストケースで、この関数はプログラムの実行開始時に、採点プログラムからちょうど 1 回呼び出されます。

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 について：

• 標準入力から、次の形式のデータを読み込みます。

  • 1 行目には、2 つの非負整数 $c,t$ が与えられます。

  • 続いて各テストデータが順に与えられます。各テストデータについて：

    • 1 行目には、2 つの正整数 $n,k$ が与えられます。
    • 2 行目には、$n$ 個の正整数 $a_0,a_1,\ldots,a_{n-1}$ が与えられます。

• 標準出力に、次の形式でデータを出力します。

  • 各テストデータについて、平衡度の最大値を表す正整数を 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 番目のテストデータでは、平衡度を最大にする分割の 1 つは $b_1=3,b_2=5,b_3=7$ です。元の列は $[6,5,1],[9,2],[3,10],[7,4,8]$ の 4 区間に分かれ、それぞれの中央値は $5,9,10,7$ です。したがって、平衡度は $\operatorname{Median}(\{5,9,10,7\})=9$ です。

2 番目のテストデータでは、平衡度を最大にする分割の 1 つは $b_1=2,b_2=4,b_3=6,b_4=8$ です。元の列は $[5,7],[3,10],[8,2],[9,1],[6,4]$ の 5 区間に分かれ、それぞれの中央値は $7,10,8,9,6$ です。したがって、平衡度は $\operatorname{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$ を、1 つのテストケース内のすべてのテストデータの $n$ の総和とします。すべてのテストデータで、次の条件を満たします。

• $1 \leq t \leq 20$。
• $5 \leq n \leq 10^6$、$2 \leq k \leq n$、$N \leq 10^6$。
• すべての $0 \leq i<n$ について、$1 \leq a_i \leq n$。

特別な性質 A：すべての $0 \leq i<n$ について、$a_i \leq 2$ を満たします。