I found an interesting problem on https://codeforces.com/problemset/problem/870/B:
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 ≤  10^5) — 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} ( - 10^9  ≤  a_{i} ≤  10^9).


-----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 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.

I tried it in Python, but could not do it. Can you solve it?
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
if k == 1:
    print(min(a))
elif k == 2:
    b = [a[0]] * (n - 1)
    for i in range(1, n - 1):
        b[i] = min(b[i - 1], a[i])
    c = [a[n - 1]] * (n - 1)
    for i in range(n - 3, -1, -1):
        c[i] = min(c[i + 1], a[i + 1])
    ans = - 10 ** 10
    for i in range(n - 1):
        ans = max(ans, max(b[i], c[i]))
    print(ans)
else:
    print(max(a))