对于大小为 $m$ 的可重集 $S = {x_0,x_1,\dots,x_{m - 1}}$，设其所有元素从大到小排序后的结果为 $y_0 \ge y_1 \ge \dots \ge y_{m - 1}$。定义其中位数 $\operatorname{Median}(S)$ 为其中第 $\left\lceil \frac{m}{2} \right\rceil$ 大的数，即 $\operatorname{Median}(S) = y_{\left\lceil \frac{m}{2} \right\rceil - 1}$。

注意：本题中的中位数定义与常规定义可能有所不同。

给定一个长度为 $n$ 的序列 $[a_0,a_1,\dots,a_{n - 1}]$，以及一个正整数 $k\ (k \le n)$。

定义一个划分如下：选择一个长度为 $k - 1$ 的递增下标序列 $0 < b_1 < \dots < b_{k - 1} < n$，将原序列划分为 $k$ 个非空段，对应的下标区间依次为

$[0,b_1),[b_1,b_2),\dots,[b_{k - 1},n)$。

对于一个划分，定义其平衡度如下：计算每个段中所有元素组成的可重集的中位数，再计算这 $k$ 个中位数组成的可重集的中位数。最终得到的数即为该划分的平衡度。

形式化地，对于划分 $b_1,b_2,\dots,b_{k - 1}$，令 $b_0 = 0$，$b_k = n$。对于每个 $0 \le i < k$，令

$c_i = \operatorname{Median}({a_{b_i},a_{b_i + 1},\dots,a_{b_{i + 1} - 1}})$，

则该划分的平衡度为 $\operatorname{Median}({c_0,c_1,\dots,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$ 是一个长度为 $n$ 的序列，表示给定的序列。
• 该函数需要返回所有划分中平衡度的最大值。
• 对于每个测试点，该函数会被评测程序调用恰好 $t$ 次。

本试题目录下的 template_median.cpp 是提供的示例代码，选手可参考并实现自己的代码。

测试程序方式

选手可以在本题目录下使用如下命令编译得到可执行文件：

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

对于编译得到的可执行文件 median：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行包含两个非负整数 $c,t$。

  • 接下来依次输入 $t$ 组测试数据。对于每组测试数据：

    • 第一行包含两个正整数 $n,k$。
    • 第二行包含 $n$ 个正整数 $a_0,a_1,\dots,a_{n - 1}$。

• 可执行文件将输出以下格式的数据至标准输出：

  • 对于每组测试数据，输出一行一个正整数，表示所有划分中平衡度的最大值。

样例一

input

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

output

9
8

explanation

对于第一组测试数据，一种平衡度最大的划分为 $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$。

样例二

见下发文件 median/median2.in 与 median/median2.ans。

该样例满足测试点 $6$ 的约束条件。

样例三

见下发文件 median/median3.in 与 median/median3.ans。

该样例满足测试点 $9$ 的约束条件。

样例四

见下发文件 median/median4.in 与 median/median4.ans。

该样例满足测试点 $14$ 的约束条件。

样例五

见下发文件 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$。

时间限制：$\texttt{1s}$

空间限制：$\texttt{1GB}$