← 返回题目列表

Codeforces · 1370/D

D. 奇偶子序列

中文机器翻译题面 查看原题

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