D. Med-imize
binary search; dp; greedy
Given two positive integers \(n\) and \(k\), and another array \(a\) of \(n\) integers.In one operation, you can select any subarray of size \(k\) of \(a\), then remove it from the array without changing the order of other elements. More formally, let \((l, r)\) be an operation on subarray \(a_l, a_{l+1}, \ldots, a_r\) such that \(r-l+1=k\), then performing this operation means replacing \(a\) with \([a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]\).For example, if \(a=[1,2,3,4,5]\) and we perform operation \((3,5)\) on this array, it will become \(a=[1,2]\). Moreover, operation \((2, 4)\) results in \(a=[1,5]\), and operation \((1,3)\) results in \(a=[4,5]\). You have to repeat the operation while the length of \(a\) is greater than \(k\) (which means \(|a| \gt k\)). What is the largest possible median\(^\dagger\) of all remaining elements of the array \(a\) after the process?\(^\dagger\)The median of an array of length \(n\) is the element whose index is \(\left \lfloor (n+1)/2 \right \rfloor\) after we sort the elements in non-decreasing order. For example: \(median([2,1,5,4,3]) = 3\), \(median([5]) = 5\), and \(median([6,8,2,4]) = 4\).
The first line contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases.The first line of each test case contains two integers \(n\) and \(k\) (\(1 \le n, k \le 5 \cdot 10^5\)).The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — the array \(a\).It is guaranteed that the sum of \(n\) over all test cases does not exceed \(5 \cdot 10^5\).
For each test case, print a single integer — the largest median possible after performing the operations.
In the first test case, you can select a subarray \((l, r)\) which can be either \((1, 3)\) or \((2, 4)\). Thus, two obtainable final arrays are \([3]\) and \([2]\). The former one has the larger median (\(3 > 2\)) so the answer is \(3\).In the second test case, three obtainable final arrays are \([6, 4]\), \([3, 4]\), and \([3, 2]\). Their medians are \(4\), \(3\), and \(2\) respectively. The answer is \(4\).In the third test case, only one element is left in the final array and it can be any element of the initial array. The largest one among them is \(9\), so the answer is \(9\).