CF1993D Med-imize

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 $ .