给定两个正整数 $$$n$$$ 和 $$$k$$$,以及另一个 $$$n$$$ 整数数组 $$$a$$$。
在一次操作中,您可以选择 $$$a$$$ 中任意大小为 $$$k$$$ 的子数组,然后将其从数组中删除,而无需更改其他元素的顺序。更正式地说,令 $$$(l, r)$$$ 为对子数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 的操作,使得 $$$r-l+1=k$$$,那么执行此操作意味着将 $$$a$$$ 替换为 $$$[a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]$$$。
例如,如果$$$a=[1,2,3,4,5]$$$,我们对该数组执行操作$$$(3,5)$$$,它将变成$$$a=[1,2]$$$。此外,操作$$$(2, 4)$$$导致$$$a=[1,5]$$$,操作$$$(1,3)$$$导致$$$a=[4,5]$$$。
当$$$a$$$的长度大于$$$k$$$时(这意味着$$$|a| \gt k$$$),您必须重复该操作。处理后数组 $$$a$$$ 中所有剩余元素的最大可能中位数 $$$^\dagger$$$ 是多少?
$$$^\dagger$$$长度为$$$n$$$的数组的中位数是我们对元素进行非降序排序后索引为$$$\left \lfloor (n+1)/2 \right \rfloor$$$的元素。例如:$$$median([2,1,5,4,3]) = 3$$$、$$$median([5]) = 5$$$ 和 $$$median([6,8,2,4]) = 4$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 执行操作后可能的最大中位数。
示例
输入 #1
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
输出 #1
3 4 9 6 4
注意
在第一个测试用例中,您可以选择一个子数组 $$$(l, r)$$$,它可以是 $$$(1, 3)$$$ 或 $$$(2, 4)$$$。因此,两个可获得的最终数组是$$$[3]$$$和$$$[2]$$$。前一个的中位数较大 ($$$3 > 2$$$),因此答案为 $$$3$$$。
在第二个测试用例中,可获得的三个最终数组是 $$$[6, 4]$$$、$$$[3, 4]$$$ 和 $$$[3, 2]$$$。它们的中位数分别为 $$$4$$$、$$$3$$$ 和 $$$2$$$。答案是$$$4$$$。
在第三个测试用例中,最终数组中只剩下一个元素,并且它可以是初始数组的任何元素。其中最大的是$$$9$$$,所以答案是$$$9$$$。