奇偶子序列

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的数组 $a$。

数组 $a$ 的子序列是指：从 $a$ 中删除若干元素（也可以不删除），且不改变剩余元素的相对顺序后得到的序列。

设 $s$ 是 $a$ 的一个子序列。定义 $s$ 的代价为下列两个值中的较小者：

• $s$ 中所有奇数位置元素的最大值；
• $s$ 中所有偶数位置元素的最大值。

这里的位置指元素在 $s$ 中的位置，而不是在 $a$ 中的位置，且位置从 $1$ 开始编号。因此，

$$\operatorname{cost}(s)=\min\bigl(\max(s_1,s_3,s_5,\ldots),\max(s_2,s_4,s_6,\ldots)\bigr).$$

例如，子序列 $\{7,5,6\}$ 的代价为 $\min(\max(7,6),\max(5))=5$。

请找出长度恰为 $k$ 的子序列的最小可能代价。

输入格式

第一行包含两个整数 $n,k$，分别表示数组长度和所需子序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示长度恰为 $k$ 的子序列的最小可能代价。

样例输入 1

4 2
1 2 3 4

样例输出 1

1

样例输入 2

4 3
1 2 3 4

样例输出 2

2

样例输入 3

5 3
5 3 4 2 6

样例输出 3

2

样例输入 4

6 4
5 3 50 2 4 5

样例输出 4

3

数据范围

对于所有数据，$2\le k\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。

子任务编号	分值	特殊限制
1	24	$n \le 20$
2	20	$k = 2$
3	28	$n \le 2000$
4		无特殊限制

提示

在样例一中，可以选择子序列 $\{1,3\}$，其代价为 $1$。

在样例二中，可以选择子序列 $\{1,2,4\}$，其代价为 $2$。

在样例四中，可以选择子序列 $\{3,50,2,4\}$，其代价为 $3$。