對於大小為 $m$ 的多重集合 $S=\{x_0,x_1,\ldots,x_{m-1}\}$，設其所有元素從大到小排序後的結果為 $y_0\ge y_1\ge\cdots\ge 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\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=\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

說明

對於第一組測試資料，一種平衡度最大的劃分為 $b_1=3$，$b_2=5$，$b_3=7$，其將原序列劃分為 $4$ 個段 $[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$ 個段 $[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\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$。