[JRKSJ R9] 在相思树下 III

>我知 > >再迷恋他也非我能私有 > >就当神爱世人遥远温柔 > >未必要牵手 > >隔千万光年宇宙献吻 > >亦真切感受 > >不用 > >强求 > >对号入座那虚构

给你一个长为 $n$ 的序列 $a_{1\dots n}$，你需要对它进行两种操作共 $n-1$ 次。 对一个长度为 $l$ 的序列 $b_{1\dots l}$ 进行一次操作将会把序列变为一个长为 $l-1$ 的序列 $c_{1\dots l-1}$： - 操作一中，$\forall i\in[1,l),c_i=\max(b_i,b_{i+1})$； - 操作二中，$\forall i\in[1,l),c_i=\min(b_i,b_{i+1})$。 给定整数 $m$，你只能进行**至多** $m$ 次操作一。进行 $n-1$ 次操作后序列 $a$ 的长度变为 $1$。你可以任意安排操作的顺序，求最终剩余的数 $a_1$ 的最大值。

第一行两个整数 $n,m$。 第二行 $n$ 个整数 $a_i$ 表示初始序列。

一个整数，代表最终剩余的数的最大可能值。

4 2
1 2 3 3

3

### 样例解释 一种可能的操作顺序是： - 进行一次操作一，序列变为 $2,3,3$； - 进行一次操作二，序列变为 $2,3$； - 进行一次操作一，序列变为 $3$。 显然最终剩余的数不可能大于 $3$。 ### 数据规模与约定 **本题采用捆绑测试。** | $\mathrm{Subtask}$ | $n\le$ | 特殊性质 | 分数 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | | $10$ | | $2$ | $5000$ | | $30$ | | $3$ | $10^6$ | $\checkmark$ | $20$ | | $4$ | $10^6$ | | $40$ | 特殊性质：保证 $\forall i\in[1,n],a_i\le10$。 对于所有数据，保证 $1\leq m < n \leq 10^6$，$1 \leq a_i \leq 10^{9}$。