對大小為 $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 入面，實作以下兩個函數：

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$，將原序列分成四段 $[6,5,1],[9,2],[3,10],[7,4,8]$。各段嘅元素中位數分別係 $5,9,10,7$，所以呢個劃分嘅平衡度係 $\operatorname{Median}(\{5,9,10,7\})=9$。

對第二組測試數據，一個平衡度最大嘅劃分係 $b_1=2,b_2=4,b_3=6,b_4=8$，將原序列分成五段 $[5,7],[3,10],[8,2],[9,1],[6,4]$。各段嘅元素中位數分別係 $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\sim 20$ 嘅限制條件。

數據範圍

用 $N$ 表示單個測試點內，所有測試數據嘅 $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$。