Ashish 有一个大小为 $$$n$$$ 的数组 $$$a$$$。
$$$a$$$ 的子序列被定义为可以通过删除一些元素(可能没有)从 $$$a$$$ 获得的序列,而不改变剩余元素的顺序。
考虑 $$$a$$$ 的子序列 $$$s$$$。他将 $$$s$$$ 的成本定义为以下两者之间的最小值:
- 奇数索引 $$$s$$$ 处的所有元素中的最大值。
- 偶数索引 $$$s$$$ 处的所有元素中的最大值。
请注意,元素的索引是其在 $$$s$$$ 中的索引,而不是其在 $$$a$$$ 中的索引。位置从 $$$1$$$ 开始编号。因此,$$$s$$$ 的成本等于 $$$min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$$$。
例如,$$$\{7, 5, 6\}$$$ 的成本为 $$$min( max(7, 6), max(5) ) = min(7, 5) = 5$$$。
帮助他找到大小为 $$$k$$$ 的子序列的最小成本。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq k \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的大小和子序列的大小。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。
输出
输出单个整数 — 大小为 $$$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
注意
在第一个测试中,考虑子序列 $$$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$$$。