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.

Difficulty: interview

Starter code:

Solutions:
n,k = map(int,input().split())
a = list(map(int,input().split()))
if k==1:
    print(min(a))
elif k==2:
    print(max(a[0],a[-1]))
else:
    print(max(a))

n,k=list(map(int,input().split()))
a=[int(i) for i in input().split()]
if (k==1):
    print(min(a))
elif (k>=3):
    print(max(a))
else:
    print(max(a[0],a[-1]))


import math
import re


def ria():
    return [int(i) for i in input().split()]


def ri():
    return int(input())


def rfa():
    return [float(i) for i in input().split()]


n, k = ria()
ar = ria()
if k == 1:
    print(min(ar))
    return
if k == 2:
    print(max(min(ar[1:]),min(ar[:-1]), ar[0], ar[-1]))
    return

print(max(ar))

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if k >= 3:
    print(max(a))
    return
if k == 1:
    print(min(a))
    return
mn = [10 ** 9 + 1] * n
mn[0] = a[0]
for i in range(1, n):
    mn[i] = min(mn[i - 1], a[i])
mnn = 10 ** 9 + 1
ans = - 10 ** 9 - 1
for i in range(n - 1, -1, -1):
    mnn = min(mnn, a[i])
    ans = max(ans, max(mnn, mn[i - 1]))
print(ans)

l, k = list(map(int, input().split()))
a = list(map(int, input().split()))
if k >= 3:
    print(max(a))
else:
    if k == 1:
        print(min(a))
    else:
        if a[0] > a[-1]:
            print(max(a[0], min(a[1:])))
        else:
            print(max(a[-1], min(a[:-1])))





#!/usr/bin/env python3

def m(k, a):
    if (k == 1):
        return min(a)
    elif (k == 2):
        return max(a[0], a[-1])
    else:
        return max(a)

def __starting_point():
    _, k = list(map(int, input().split()))
    print(m(k, list(map(int, input().split()))))

__starting_point()

n, k = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
    print(min(a))
elif k >= 3:
    print(max(a))
else:
    print(max(a[0], a[-1]))

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def main():
    n, k = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    if k == 1:
        print(min(arr))
    elif k == 2:
        print(max(arr[0], arr[-1]))
    else:
        print(max(arr))
def __starting_point():
    main()

__starting_point()

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


n, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]
if k == 1 or n == 1:
    print(min(a))
elif k >= 3:
    print(max(a))
else:
    print(max(a[0], a[-1]))
        
        


a = int(input().split()[1])
list1 = list(map(int, input().split()))

if a == 1:
    min1 = list1[0]
    for i in list1:
        if min1 > i:
            min1 = i
    print(min1)
elif a >= 3:
    max1 = list1[0]
    for i in list1:
        if max1 < i:
            max1 = i
    print(max1)
elif a == 2:
    min1 = list1[0]
    min2 = list1[-1]
    if min1 > min2:
        print(min1)
    else:
        print(min2)


n, k = tuple(map(int, input().split()))
a = list(map(int, input().split()))
if k == 1:
	print(min(a))
elif k == 2:
	print(max(a[0], a[-1]))
else:
	print(max(a))


n, k = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
    print(min(a))
elif k == 2:
    print(max(a[0],a[-1]))
else:
    print(max(a))

from sys import stdin as fin
# fin = open("tc172b.in", "r")

# n = int(fin.readline())
n, k = map(int, fin.readline().split())
arr = list(map(int, fin.readline().split()))
# s = fin.readline().rstrip()

if k >= 3:
    print(max(arr))
elif k == 1:
    print(min(arr))
else:
    print(max(arr[0], arr[-1]))

a, b = map(int, input().split())
c = input().split()
max1 = -1000000000
for i in range (a):
    if int(max1) < int(c[i]):
        ma = i
        max1 = c[i]
min1 = 10000000000
for i in range (a):
    if int(min1) > int(c[i]):
        min1 = c[i]
        mi1 = i
if b >= 3:
    print(max1)
elif b == 1:
    print(min1)
elif b == 2:
    if int(c[0]) < int(c[a - 1]):
        print(int(c[a - 1]))
    else:
        print(int(c[0]))

n , k = [int(z) for z in input().split()]
a = [int(z) for z in input().split()]
kek = max(a)
if k > 2:
    print(kek)
    return
if k > 1:
    print(max(a[0], a[-1]))   
else:
    print(min(a))

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if k == 1:
    print(min(a))
elif k > 2:
    print(max(a))
else:
    print(max(a[0], a[-1]))


n, k = map(int, input().split())
l = [int(x) for x in input().split()]
sl = []
sr = [0 for i in range(n)]
m = -10000000000
if k == 1:
  print(min(l))
elif k > 2:
  print(max(l))
else:
  sl.append(l[0])
  for i in range(1, n):
    sl.append(min(sl[i-1], l[i]))
    
  sr[n-1] = l[n-1]
  for i in range(n-2, -1, -1):
    sr[i] = min(sr[i+1], l[i])

  for i in range(0, n-1):
    m = max(m, sl[i], sr[i+1])

  print(m)

n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
if k==1:
    print(min(a))
elif k==2:
    b=max(a[0],a[-1])
    c=min(a)
    z=min(a[a.index(min(a)):])
    print(max(b,c,z))
else:
    print(max(a))


n, k = map(int, input().split())
arr = list(map(int, input().split()))
if k == 1:
    print(min(arr))
    return
elif k == 2:
    print(max(arr[0], arr[-1]))
else:
    print(max(arr))

n, k = map(int,input().split())
a = list(map(int,input().split()))
if k == 1:
    print(min(a))
elif k == 2:
    print(max(a[0],a[len(a) - 1]))
else:
    print(max(a))

n, k = list(map(int, input().split()))
l1 = list(map(int, input().split()))
l11 = []
l_s = []
m_v = 0
for ev in l1:
    l11.append(ev)
    l_s.append(ev)
l_s.sort()
if (k == 1):
    print(int(min(l11)))
elif (k >= 3):
    print(int(max(l11)))
elif (k == 2):
    if l11[0] > l11[n - 1] and l11[0] != l_s[0]:
        print(l11[0])
    elif l11[0] < l11[n - 1] and l11[n - 1] != l_s[0]:
        print(l11[n - 1])
    else:
        print(l11[0])


n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
x=0
if k==1:
    x=min(a)
elif k==2:
    x=max(a[0],a[n-1])
else:
    x=max(a)
print(x)

#print(" ".join(map(str,a)))


a = [int(s) for s in input().split()]
b = [int(s) for s in input().split()]
if (a[1] == 1):
    minimum = b[0]
    for i in range(a[0]):
        if (minimum > b[i]):
            minimum = b[i]
    print(minimum)
elif (a[1] >= 3):
    maximum = b[0]
    for i in range(a[0]):
        if (maximum < b[i]):
            maximum = b[i]
    print(maximum)
elif (a[1] == 2 and a[0] == 2):
    print(max(b[0], b[1]))
else:
    print(max(b[0], b[a[0] - 1]))