Background

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.

Problem Description

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$.

Input Format

The first line contains two integers $n,m$.

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

Output Format

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

4 2
1 2 3 3

3

Hint

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.

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