题目描述

给定长度为 $n$ 的非负整数序列 $a_i$，还有一个参数 $k$。

如果当前序列中的数字个数大于 $k$ 个，你 必须 选择一段连续的、长度恰好为 $k$ 的区间，并将这个区间内的所有数字删除，并将剩下的数字按原顺序拼起来。

例如原序列为 $[3,6,1,7,5,2,8],k = 3$ 你可以先删除 $[2,4]$ 使得序列变成 $[3,5,2,8]$，然后可以删除 $[2,4]$ 使得序列变为 $[3]$。

求你所有可能的删数方案中，最后数组中留下的数字的中位数最大是多少。

中位数：所有数字排序后中间的那个数。例如 $[5,1,4]$ 的中位数是 $4$，$[4,6,2,5]$ 的中位数也是 $4$。

输入格式

第一行一个正整数 $T$，表示 $T$ 组询问。对于每组询问：

第一行两个正整数 $n,k$，表示数字数量、删除的参数。

接下来一行 $n$ 个非负整数，表示 $a_i$。

输出格式

对于每组询问，输出一个非负整数表示答案。

5
4 3
3 9 9 2
5 3
3 2 5 6 4
7 1
5 9 2 6 5 4 6
8 2
7 1 2 6 8 3 4 5
4 5
3 4 5 6

3
4
9
6
4

样例解释

对于第一组询问，删去 $[2,4]$ 即可。

数据规模与约定

下发文件

下发文件对应子任务 $4,5,6$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^4,1 \leq n,k \leq 5 \times 10^{5},\sum n \leq 5 \times 10^5,0 \leq a_i \leq 10^9$。