题目描述

Ashish 拥有一个大小为 $n$ 的数组 $a$。

数组 $a$ 的子序列定义为：通过从 $a$ 中删除若干元素（可以不删除），且不改变剩余元素相对顺序得到的序列。

设 $s$ 为 $a$ 的一个子序列，他定义子序列 $s$ 的代价为以下两个值的最小值：

• $s$ 中奇数下标元素的最大值；
• $s$ 中偶数下标元素的最大值。

注意：元素的下标是它在子序列 $s$ 中的下标，而非在原数组 $a$ 中的下标，位置从 $1$ 开始编号。 因此，子序列的代价公式为：

$$\textit{cost} = \min\left(\max(s_1,s_3,s_5,\dots),\max(s_2,s_4,s_6,\dots)\right) $$

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

请你帮他找出：长度恰好为 $k$ 的子序列的最小代价。

---

输入格式

第一行包含两个整数 $n$ 和 $k$（$2 \le k \le n \le 2 \cdot 10^5$），分别表示原数组大小和目标子序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），表示原数组元素。

---

输出格式

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

---

样例输入

4 2
1 2 3 4

4 3
1 2 3 4

5 3
5 3 4 2 6

6 4
5 3 50 2 4 5

样例输出

1
2
2
3

---

样例说明

• 第一个测试用例：选择子序列 $s = \{1,3\}$，代价为 $\min(\max(1),\max(3))=1$。
• 第二个测试用例：选择子序列 $s = \{1,2,4\}$，代价为 $\min(\max(1,4),\max(2))=2$。
• 第四个测试用例：选择子序列 $s = \{3,50,2,4\}$，代价为 $\min(\max(3,2),\max(50,4))=3$。