P10878 [JRKSJ R9] Under the Acacia Tree III.

> I know. > > No matter how much I am obsessed with him, he cannot be mine alone. > > Just treat it as God loving the world, distant and gentle. > > Holding hands is not necessary. > > Across tens of millions of light-years, the universe offers a kiss. > > It can still be felt clearly. > > No need. > > To force it. > > To fit yourself into that made-up role.

You are given a sequence $a_{1\dots n}$ of length $n$. You need to perform two types of operations on it for a total of $n-1$ times. For a sequence $b_{1\dots l}$ of length $l$, performing one operation will turn it into a sequence $c_{1\dots l-1}$ of length $l-1$: - In operation 1, $\forall i\in[1,l),c_i=\max(b_i,b_{i+1})$. - In operation 2, $\forall i\in[1,l),c_i=\min(b_i,b_{i+1})$. Given an integer $m$, you can perform operation 1 at most $m$ times. After performing $n-1$ operations, the length of sequence $a$ becomes $1$. You may arrange the order of operations arbitrarily. Find the maximum possible value of the final remaining number $a_1$.

The first line contains two integers $n,m$. The second line contains $n$ integers $a_i$, representing the initial sequence.

Output one integer, representing the maximum possible value of the final remaining number.

### Sample Explanation One possible order of operations is: - Perform operation 1 once, and the sequence becomes $2,3,3$. - Perform operation 2 once, and the sequence becomes $2,3$. - Perform operation 1 once, and the sequence becomes $3$. Obviously, the final remaining number cannot be greater than $3$. ### Constraints **This problem uses bundled testdata.** | $\mathrm{Subtask}$ | $n\le$ | Special property | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | | $10$ | | $2$ | $5000$ | | $30$ | | $3$ | $10^6$ | $\checkmark$ | $20$ | | $4$ | $10^6$ | | $40$ | Special property: it is guaranteed that $\forall i\in[1,n],a_i\le10$. For all data, it is guaranteed that $1\leq m < n \leq 10^6$, and $1 \leq a_i \leq 10^{9}$. Translated by ChatGPT 5