You are given an array a1, a2, ..., an 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 a1, a2, ..., an ( - 109 ≤ ai ≤ 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.

Examples

Input

5 2
1 2 3 4 5


Output

5


Input

5 1
-4 -5 -3 -2 -1


Output

-5

Note

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

Splitting of array a of n elements into k subsegments [l1, r1], [l2, r2], ..., [lk, rk] (l1 = 1, rk = n, li = ri - 1 + 1 for all i > 1) is k sequences (al1, ..., ar1), ..., (alk, ..., ark).

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.
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9 + 113;
const long long maxn = 1e5 + 113;
int main() {
  srand(time(NULL));
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  vector<int> s1;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    s1.push_back(a);
  }
  int ans = s1[0];
  if (k == 1) {
    for (int i = 0; i < n; i++) ans = min(ans, s1[i]);
    cout << ans;
    return 0;
  }
  int maxn = s1[0];
  for (int i = 0; i < n; i++) maxn = max(maxn, s1[i]);
  if (k >= 3) {
    cout << maxn;
    return 0;
  }
  if (k == 2) {
    cout << max(s1[0], s1[s1.size() - 1]);
    return 0;
  }
}
