CF870B.Maximum of Maximums of Minimums

You are given an array _a_1, _a_2, ..., a__n consisting of n integers, and an integer k. You have to split the array into exactly k non-empty subsegments. You'll then compute the minimum integer on each subsegment, and take the maximum integer over the k obtained minimums. What is the maximum possible integer you can get?

Definitions of subsegment and array splitting are given in notes.

给你一个由 $n$ 个整数组成的数组 $a_1,\,a_2,\,\dots,\,a_n$，以及一个整数 $k$。你需要将该数组恰好划分为 $k$ 个非空子段（subsegment）。接着，对每个子段分别计算其最小值，再从这 $k$ 个最小值中取最大值。问：你能得到的最大可能值是多少？

子段（subsegment）与数组划分（array splitting）的定义见“注释”部分。

The first line contains two integers n and k (1 ≤ k ≤ n ≤  105) — the size of the array a and the number of subsegments you have to split the array to.

The second line contains n integers _a_1,  _a_2,  ...,  a__n ( - 109  ≤  a__i ≤  109).

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 10^5$）—— 分别表示数组 $a$ 的大小以及你需要将数组划分成的子区间个数。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$-10^9 \le a_i \le 10^9$）。

Print single integer — the maximum possible integer you can get if you split the array into k non-empty subsegments and take maximum of minimums on the subsegments.

输出一个整数——即当把数组划分为 $k$ 个非空子段，并对每个子段取最小值后再取这些最小值中的最大值时，所能得到的最大可能整数。

A subsegment [l,  r] (l ≤ r) of array a is the sequence a__l,  a__l + 1,  ...,  a__r.

Splitting of array a of n elements into k subsegments [_l_1, _r_1], [_l_2, _r_2], ..., [l__k, r__k] (_l_1 = 1, r__k = n, l__i = r__i - 1 + 1 for all i > 1) is k sequences (_a__l_1, ..., _a__r_1), ..., (a__l__k, ..., a__r__k).

In the first example you should split the array into subsegments [1, 4] and [5, 5] that results in sequences (1, 2, 3, 4) and (5). The minimums are min(1, 2, 3, 4) = 1 and min(5) = 5. The resulting maximum is max(1, 5) = 5. It is obvious that you can't reach greater result.

In the second example the only option you have is to split the array into one subsegment [1, 5], that results in one sequence ( - 4,  - 5,  - 3,  - 2,  - 1). The only minimum is min( - 4,  - 5,  - 3,  - 2,  - 1) =  - 5. The resulting maximum is  - 5.

数组 $a$ 的一个子段 $[l,\,r]$（其中 $l \le r$）是指序列 $a_l,\, a_{l+1},\, \dots,\, a_r$。

将含有 $n$ 个元素的数组 $a$ 划分为 $k$ 个子段 $[l_1,\,r_1],\, [l_2,\,r_2],\, \dots,\, [l_k,\,r_k]$（满足 $l_1 = 1$，$r_k = n$，且对所有 $i > 1$ 有 $l_i = r_{i-1} + 1$），即得到 $k$ 个序列 $(a_{l_1},\, \dots,\, a_{r_1}),\, \dots,\, (a_{l_k},\, \dots,\, a_{r_k})$。

在第一个例子中，你需要将数组划分为子段 $[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$。