Codeforces Round 963 (Div. 2) |
---|
Finished |
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.
54 33 9 9 25 33 2 5 6 47 15 9 2 6 5 4 68 27 1 2 6 8 3 4 54 53 4 5 6
3 4 9 6 4
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$$$.
Name |
---|