给定一个数组 a1, a2, ...,由 n 个整数组成,还有一个整数 k。您必须将数组精确地拆分为 k 个非空子段。然后,您将计算每个子段的最小整数,并在获得的 k 个最小值上取最大整数。你能得到的最大可能整数是多少?
子段和数组分割的定义在注释中给出。
输入
第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 105) — 数组 a 的大小以及必须将数组拆分为的子段数。
第二行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109)。
输出
打印单个整数 - 如果将数组拆分为 k 个非空子段并在子段上取最小值中的最大值,则可以获得的最大可能整数。
示例
输入 #1
5 2 1 2 3 4 5
输出 #1
5
输入 #2
5 1 -4 -5 -3 -2 -1
输出 #2
-5
注意
数组 a 的子段 [l, r] (l ≤ r) 是序列 al, al + 1, ..., ar。
将 n 个元素的数组 a 拆分为 k 个子段 [l1, r1], [l2, r2], ..., [lk, rk](l1 = 1, rk = n, li = ri - 1 + 1 对于所有 i > 1)是 k 个序列 (al1, ..., ar1), ..., (alk, ..., ark)。
在第一个示例中,您应该将数组拆分为子段 [1, 4] 和 [5, 5],从而生成序列 (1, 2, 3, 4) 和 (5)。最小值为 min(1, 2, 3, 4) = 1 和 min(5) = 5。所得最大值为 max(1, 5) = 5。显然,您无法获得更大的结果。
在第二个示例中,您唯一的选择是将数组拆分为一个子段 [1, 5],从而产生一个序列 (- 4, - 5, - 3, - 2, - 1)。唯一的最小值为 min( - 4, - 5, - 3, - 2, - 1) = - 5。生成的最大值为 - 5。