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$。"}]
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 10^5 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in [-10^9, 10^9] $ for all $ i \in \{1, \dots, n\} $.
A **splitting** of $ A $ into $ k $ non-empty subsegments is a sequence of indices $ 1 = l_1 \leq r_1 < l_2 \leq r_2 < \dots < l_k \leq r_k = n $ such that for all $ i \in \{2, \dots, k\} $, $ l_i = r_{i-1} + 1 $, and each subsegment is $ S_i = (a_{l_i}, a_{l_i+1}, \dots, a_{r_i}) $.
For each subsegment $ S_i $, define $ m_i = \min(S_i) $.
Define $ M = \max\{m_1, m_2, \dots, m_k\} $.
**Objective**
Maximize $ M $ over all possible splittings of $ A $ into exactly $ k $ non-empty contiguous subsegments.