P17143 [NOI 2026] Median

The statement and sample attachments come from [QOJ](https://qoj.ac/contest/3939/problem/18986)。 When submitting to Luogu, there is no need to include the header `#include "median.h"`。Just copy ```cpp void init(int c, int t); int median(int n, int k, std::vector a); ``` to the beginning of your program, and compile with a C++17 or higher compiler。

For a multiset $S=\{x_0,x_1,\ldots,x_{m-1}\}$ of size $m$, let the result of sorting all its elements **from large to small** be $y_0\ge y_1\ge\cdots\ge y_{m-1}$。Define its **median** $\operatorname{Median}(S)$ as the $\left\lceil\frac{m}{2}\right\rceil$-th largest number, i.e., $\operatorname{Median}(S)=y_{\left\lceil\frac{m}{2}\right\rceil-1}$。**Note: the definition of median in this problem may be different from the usual definition。** Given a sequence of length $n$, $[a_0,a_1,\ldots,a_{n-1}]$, and a positive integer $k$ ($k\le n$)。Define a **partition** as follows: choose an increasing index sequence of length $k-1$, $0

### 【Grader Program Method】 Contestants can compile an executable in this problem directory using the following command: ```bash g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static ``` For the compiled executable file `median`: - The executable will read input from standard input in the following format: - The first line contains two non-negative integers $c,t$。 - Then follow the testdata groups in order。For each testdata group: - The first line contains two positive integers $n,k$。 - The second line contains $n$ positive integers $a_0,a_1,\ldots,a_{n-1}$。 - The executable will output to standard output in the following format: - For each testdata group, output one line containing one positive integer, representing the maximum balance value。

N/A

### 【Sample $1$ Explanation】 For the first testdata group, one partition with the maximum balance value is $b_1=3$，$b_2=5$，$b_3=7$。It partitions the original sequence into $4$ segments $[6,5,1]$、$[9,2]$、$[3,10]$、$[7,4,8]$。The medians of the elements in the segments are $5,9,10,7$ respectively, so the balance value of this partition is $\operatorname{Median}(\{5,9,10,7\})=9$。 For the second testdata group, one partition with the maximum balance value is $b_1=2$，$b_2=4$，$b_3=6$，$b_4=8$。It partitions the original sequence into $5$ segments $[5,7]$、$[3,10]$、$[8,2]$、$[9,1]$、$[6,4]$。The medians of the elements in the segments are $7,10,8,9,6$ respectively, so the balance value of this partition is $\operatorname{Median}(\{7,10,8,9,6\})=8$。 ### 【Sample $2$】 See `median/median2.in` and `median/median2.ans` in the contestant directory。 This sample satisfies the constraints of test point $6$。 ### 【Sample $3$】 See `median/median3.in` and `median/median3.ans` in the contestant directory。 This sample satisfies the constraints of test point $9$。 ### 【Sample $4$】 See `median/median4.in` and `median/median4.ans` in the contestant directory。 This sample satisfies the constraints of test point $14$。 ### 【Sample $5$】 See `median/median5.in` and `median/median5.ans` in the contestant directory。 This sample satisfies the constraints of test points $18\sim20$。 ### 【Constraints】 Let $N$ be the sum of $n$ over all testdata within a single test point。For all testdata, we have: - $1\le t\le20$； - $5\le n\le10^6$，$2\le k\le n$，$N\le10^6$； - For all $0\le i5$ | ^ | | $18\sim20$ | ^ | ^ | $\le n$ | ^ | Special property $A$: for all $0\le i