「DTOI-4」中位数
题目描述
给定一个长度为 $n$ 的整数序列 $a$，你可以进行以下操作不超过 $k$ 次：
- 选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq n$，并将 $[l, r]$ 中的所有数替换为这个区间的中位数。
你要使得操作后 $a$ 的**最小值最大**。
关于此处中位数的定义：对于一个长度为 $len$ 的序列，其中位数定义为该序列中第 $\lceil \frac{len}{2} \rceil$ 小的数。
输入输出格式
输入格式
第一行，两个整数 $n, k$；
第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$。
输出格式
一行，表示经过不超过 $k$ 次操作后序列最小值的最大值。
输入输出样例
输入样例 #1
10 2
2 8 3 2 5 7 10 4 9 7输出样例 #1
7输入样例 #2
30 3
1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0输出样例 #2
0输入样例 #3
31 3
1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1输出样例 #3
1说明
| $\textbf{Subtask}$ | $n$ | 分值 |
| :------: | :------: | :------: |
| $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$ | 无特殊限制 | $30 \operatorname{pts}$ |
对于 $100\%$ 的数据，$1 \leq n \leq 4 \times 10^5$，$0 \leq k \leq n$，$0 \leq a_i \leq 10^9$。