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.
## Input
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).
## Output
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.
[samples]
## Note
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.
[{"iden":"statement","content":"你被给定一个包含 $n$ 个整数的数组 $[a_1, a_2, ..., a_n]$ 和一个整数 $k$。你需要将数组恰好分割为 $k$ 个非空子段。然后，你将计算每个子段中的最小整数，并取这 $k$ 个最小值中的最大值。你能获得的最大可能整数是多少？\n\n子段和数组分割的定义见注释。\n\n第一行包含两个整数 $n$ 和 $k$ ($1 ≤ k ≤ n ≤ 10^5$) —— 数组 $a$ 的大小以及你需要将其分割成的子段数量。\n\n第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($ - 10^9 ≤ a_i ≤ 10^9$)。\n\n请输出一个整数 —— 如果你将数组分割为 $k$ 个非空子段并取各子段最小值中的最大值，你能得到的最大可能整数。\n\n数组 $a$ 的子段 $[l, r]$ ($l ≤ r$) 是序列 $a_l, a_{l+1}, ..., a_r$。\n\n将包含 $n$ 个元素的数组 $a$ 分割为 $k$ 个子段 $[l_1, r_1], [l_2, r_2], ..., [l_k, r_k]$（其中 $l_1 = 1$, $r_k = n$, 且对所有 $i > 1$ 有 $l_i = r_{i-1} + 1$）是指 $k$ 个序列 $(a_{l_1}, ..., a_{r_1}), ..., (a_{l_k}, ..., a_{r_k})$。\n\n在第一个例子中，你应该将数组分割为子段 $[1, 4]$ 和 $[5, 5]$，从而得到序列 $(1, 2, 3, 4)$ 和 $(5)$。最小值分别为 $\min(1, 2, 3, 4) = 1$ 和 $\min(5) = 5$。最终的最大值为 $\max(1, 5) = 5$。显然，你无法获得更大的结果。\n\n在第二个例子中，你唯一的选择是将数组分割为一个子段 $[1, 5]$，从而得到一个序列 $( - 4, - 5, - 3, - 2, - 1)$。唯一的最小值是 $\min( - 4, - 5, - 3, - 2, - 1) = - 5$。最终的最大值是 $ - 5$。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $k$ ($1 ≤ k ≤ n ≤ 10^5$) —— 数组 $a$ 的大小以及你需要将其分割成的子段数量。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($ - 10^9 ≤ a_i ≤ 10^9$)。"},{"iden":"output","content":"请输出一个整数 —— 如果你将数组分割为 $k$ 个非空子段并取各子段最小值中的最大值，你能得到的最大可能整数。"},{"iden":"examples","content":"输入\n5 2\n1 2 3 4 5\n输出\n5\n\n输入\n5 1\n-4 -5 -3 -2 -1\n输出\n-5"},{"iden":"note","content":"数组 $a$ 的子段 $[l, r]$ ($l ≤ r$) 是序列 $a_l, a_{l+1}, ..., a_r$。\n\n将包含 $n$ 个元素的数组 $a$ 分割为 $k$ 个子段 $[l_1, r_1], [l_2, r_2], ..., [l_k, r_k]$（其中 $l_1 = 1$, $r_k = n$, 且对所有 $i > 1$ 有 $l_i = r_{i-1} + 1$）是指 $k$ 个序列 $(a_{l_1}, ..., a_{r_1}), ..., (a_{l_k}, ..., a_{r_k})$。\n\n在第一个例子中，你应该将数组分割为子段 $[1, 4]$ 和 $[5, 5]$，从而得到序列 $(1, 2, 3, 4)$ 和 $(5)$。最小值分别为 $\min(1, 2, 3, 4) = 1$ 和 $\min(5) = 5$。最终的最大值为 $\max(1, 5) = 5$。显然，你无法获得更大的结果。\n\n在第二个例子中，你唯一的选择是将数组分割为一个子段 $[1, 5]$，从而得到一个序列 $( - 4, - 5, - 3, - 2, - 1)$。唯一的最小值是 $\min( - 4, - 5, - 3, - 2, - 1) = - 5$。最终的最大值是 $ - 5$。"}]