CF1993D.Med-imize

给定两个正整数 $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| \le k$）为止。请问，经过这一过程后，所有可能剩下的 $a$ 的元素中，最大的中位数是多少？

$^\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$。

对于每个测试用例，输出一个整数，表示经过操作后可能得到的最大中位数。

在第一个测试用例中，你可以选择子数组 $(l, r)$，即 $(1, 3)$ 或 $(2, 4)$。因此，最终可能得到的数组为 $[3]$ 或 $[2]$。前者的中位数更大（$3 > 2$），所以答案是 $3$。

在第二个测试用例中，最终可能得到的数组为 $[6, 4]$、$[3, 4]$ 和 $[3, 2]$。它们的中位数分别为 $4$、$3$ 和 $2$。答案为 $4$。

在第三个测试用例中，最终只会剩下一个元素，可以是初始数组中的任意一个元素。最大值为 $9$，所以答案为 $9$。

由 ChatGPT 4.1 翻译