Problem B
Big Median
You are given an array of length $N$. You want to split it into $K$ consecutive segments (for instance, $[1,2,3,4,5]$ can be split into $[[1,2,3],[4],[5]]$).
We define the median of a segment to be the middle element if the integers in the segment were sorted. As the median of a segment with even number of elements is ambiguous, each segment must have an odd number of elements.
The strength of a grouping is defined as the smallest median among all $K$ segments. Find the maximal strength.
Input
The first line of input contains 2 space-separated integers, $N$ $(1 \leq N \leq 2000)$ and $K$ $(1 \leq K \leq N)$, size of the array and number of segments respectively. $N$ and $K$ are both guaranteed to be odd.
The second line of input contains $N$ integers, representing the array you are to split. $(0 \leq a_i \leq 10^9)$
Note: there exists a solution that solves $1 \leq N \leq 2 \cdot 10^5$. Some students may find that solution more intuitive.
Output
Output a single integer, the maximal strength of the array.
Sample 1 Explanation
One way to split the array is $[3], [3], [3,8,9]$ which will have medians $3, 3, 8$ respectively. The smallest median among them will be $3$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 3 3 3 8 9 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 3 9 8 10 2 7 6 1 |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
11 3 10 4 2 7 5 0 9 3 4 2 1 |
3 |
