P8978 "DTOI-4" Median.

Given an integer sequence $a$ of length $n$, you may perform the following operation at most $k$ times: - Choose an interval $[l, r]$ such that $1 \leq l \leq r \leq n$, and replace all numbers in $[l, r]$ with the median of this interval. You want to make the **minimum value** of $a$ as large as possible after the operations. Definition of the median here: for a sequence of length $len$, its median is defined as the $\left\lceil \frac{len}{2} \right\rceil$-th smallest number in the sequence.

The first line contains two integers $n, k$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output one line containing the maximum possible value of the minimum element of the sequence after at most $k$ operations.

| $\textbf{Subtask}$ | $n$ | Score | | :------: | :------: | :------: | | $1$ | $1 \leq n \leq 10$ | $10 \operatorname{pts}$ | | $2$ | $1 \leq n \leq 100$ | $10 \operatorname{pts}$ | | $3$ | $1 \leq n \leq 10^3$ | $10 \operatorname{pts}$ | | $4$ | $1 \leq n \leq 10^4$ | $20 \operatorname{pts}$ | | $5$ | $1 \leq n \leq 10^5$ | $20 \operatorname{pts}$ | | $6$ | No special constraints. | $30 \operatorname{pts}$ | For $100\%$ of the testdata, $1 \leq n \leq 4 \times 10^5$, $0 \leq k \leq n$, and $0 \leq a_i \leq 10^9$. Translated by ChatGPT 5