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: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from sys import stdin
(n, k) = (int(i) for i in stdin.readline().split())
nums = [int(i) for i in stdin.readline().split()]
if k >= 3:
	print(max(nums))
elif k == 1:
	print(min(nums))
else:
	print(max(nums[0], nums[-1]))


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


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


inp = input().split()
length = int(inp[0])
intervals = int(inp[1])
arr = input().split()
for i in range(length):
	arr[i] = int(arr[i])
if intervals == 1:
	print(min(arr))
elif intervals == 2:
	print(max(arr[0], arr[length - 1]))
else:
	print(max(arr))


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


I = lambda : map(int, input().split())
(_, k) = I()
A = list(I())
print(min(A) if k < 2 else max(A) if k > 2 else max(A[0], A[-1]))


(n, k) = 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))


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


(n, k) = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
mn1 = [1000000000 for x in range(n)]
mn2 = [1000000000 for x in range(n)]
mx = -10000000000
if k >= 3:
	print(max(a))
elif k == 2:
	for i in range(n):
		if i == 0:
			mn1[i] = a[i]
		else:
			mn1[i] = min(a[i], mn1[i - 1])
	for i in range(n):
		if n - i - 1 == n - 1:
			mn2[n - i - 1] = a[n - i - 1]
		else:
			mn2[n - i - 1] = min(a[n - i - 1], mn2[n - i - 1 + 1])
	for i in range(n - 1):
		mx = max(mx, max(mn1[i], mn2[i + 1]))
	print(mx)
else:
	print(min(a))


s = input().split()
(n, k) = (int(s[0]), int(s[1]))
s = input().split()
a = []
(mn, mx) = (10000000000.0, -10000000000.0)
for x in s:
	e = int(x)
	a.append(e)
	mn = min(mn, e)
	mx = max(mx, e)
ans = mx
if k == 1:
	ans = mn
elif k == 2:
	ans = max(a[0], a[n - 1])
print(ans)


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


import sys

def greedy_solution(nums, num_set):
	if num_set > 2:
		return max(nums)
	elif num_set == 2:
		return max(nums[0], nums[-1])
	else:
		return min(nums)

def main():
	line = sys.stdin.readline().split()
	(num_int, num_set) = (int(line[0]), int(line[1]))
	line = sys.stdin.readline().split()
	nums = [int(s) for s in line]
	result = greedy_solution(nums, num_set)
	sys.stdout.write('{}\n'.format(result))
main()


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
M = max(l)
m = min(l)
if k == 1:
	print(m)
elif k >= 3:
	print(M)
elif l.index(M) == 0 or l.index(M) == len(l) - 1:
	print(M)
elif l.index(m) == 0:
	print(l[len(l) - 1])
elif l.index(m) == len(l) - 1:
	print(l[0])
else:
	print(max(l[0], l[len(l) - 1]))


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


params = [int(x) for x in input().split(' ')]
nums = [int(x) for x in input().split(' ')]
nums_sorted = sorted(nums)
if params[1] > 2:
	print(nums_sorted[-1])
elif params[1] > 1:
	print(max([nums[0], nums[-1]]))
else:
	print(nums_sorted[0])


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


(n, k) = 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:
	l_min = [0] * (n - 1)
	r_min = [0] * (n - 1)
	l_min[0] = a[0]
	r_min[-1] = a[-1]
	for i in range(1, n - 1):
		l_min[i] = min(l_min[i - 1], a[i])
		r_min[-1 - i] = min(r_min[-i], a[-i - 1])
	ans = min(a)
	for i in range(n - 1):
		ans = max(l_min[i], max(r_min[i], ans))
	print(ans)


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


(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:
	pref = []
	minP = int(1000000000.0 + 7)
	suf = []
	minS = int(1000000000.0 + 7)
	for i in range(n):
		if minP > a[i]:
			minP = a[i]
		pref.append(minP)
		if minS > a[n - i - 1]:
			minS = a[n - i - 1]
		suf.append(minS)
	print(max(max(suf), max(pref)))
else:
	print(max(a))


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


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


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


(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 >= 3:
	print(max(a))
if k == 2:
	print(max(a[0], a[n - 1]))
if k == 1:
	print(min(a))


import sys
length = 0
interval = []

def get_user_input():
	global length
	global interval
	interval_info = input('').split()
	length = int(interval_info[0])
	k = int(interval_info[1])
	interval = [int(x) for x in input().split()]
	return k

def k2():
	min_values = []
	length = len(interval)
	max_val = max(interval)
	index = interval.index(max_val)
	if index == 0 or index == length - 1:
		return max_val
	min_l = sys.maxsize
	for i in range(0, length - 1):
		if interval[i] < min_l:
			min_l = interval[i]
			min_values.append(min_l)
	min_l = sys.maxsize
	for i in range(length - 1, 0, -1):
		if interval[i] < min_l:
			min_l = interval[i]
			min_values.append(min_l)
	return max(min_values)

def calc(k):
	if k == 1:
		print(min(interval))
	elif k == 2:
		print(k2())
	else:
		max_value = max(interval)
		print(max_value)
k = get_user_input()
calc(k)


(n, k) = map(int, input().split())
if k == 1:
	print(min(list(map(int, input().split()))))
elif k > 2:
	print(max(list(map(int, input().split()))))
else:
	ans = -1e+18
	a = list(map(int, input().split()))
	L = [0 for i in range(n)]
	R = [0 for i in range(n)]
	L[0] = a[0]
	R[n - 1] = a[n - 1]
	for i in range(1, n):
		L[i] = min(L[i - 1], a[i])
		R[n - i - 1] = min(R[n - i], a[n - i])
	for i in range(n):
		ans = max(ans, max(R[i], L[i]))
	print(ans)


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


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


(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) = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
	print(min(a))
	exit(0)
if k == 2:
	t = min(a)
	min1 = [0] * n
	min2 = [0] * n
	min1[0] = a[0]
	min2[-1] = a[-1]
	for i in range(1, n):
		min1[i] = min(min1[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		min2[i] = min(min2[i + 1], a[i])
	for i in range(1, n):
		q = max(min1[i - 1], min2[i])
		if q > t:
			t = q
	print(t)
	exit(0)
answ = max(a)
print(answ)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
if k > 2:
	print(max(A))
elif k == 2:
	print(max(A[0], A[len(A) - 1]))
else:
	print(min(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))
else:
	pref = [a[-1]]
	for i in range(1, n):
		pref.append(min(a[-i - 1], pref[-1]))
	pref = pref[::-1]
	(pr, ans) = (2000000000.0, min(a))
	for i in range(n - 1):
		pr = min(pr, a[i])
		ans = max([ans, pref[i + 1], pr])
	print(ans)


(n, k) = map(int, input().split())
s = [int(i) for i in input().split()]
c = 0
p = 0
if k >= 3:
	c = s[0]
	for i in range(len(s)):
		if s[i] > c:
			c = s[i]
	print(c)
if k == 1:
	c = s[0]
	for i in range(len(s)):
		if s[i] < c:
			c = s[i]
	print(c)
if k == 2:
	if s[-1] > s[0] or s[0] > s[-1]:
		print(max(s[-1], s[0]))
	else:
		print(s[0])


(n, k) = map(int, input().split())
l = [int(i) for i in input().split()]
if k == 1:
	print(min(l))
	exit()
if k == 2:
	mini = 100000000000000
	mini1 = 47548694576859
	maxi = -10000000000000
	for i in range(n):
		mini = min(mini, l[i])
		mini1 = min(mini1, l[n - 1 - i])
		maxi = max(maxi, mini, mini1)
	print(maxi)
	exit()
print(max(l))


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


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


(n, k) = input().split()
n = int(n)
k = int(k)
array = input().split()
fin = []
for i in array:
	fin.append(int(i))
i = 0
prefix = []
minm = 2 ** 31 - 1
while i < len(fin):
	if fin[i] < minm:
		minm = fin[i]
	prefix.append(minm)
	i += 1
i = len(fin) - 1
minm = 2 ** 31 - 1
suffix = []
while i >= 0:
	if fin[i] < minm:
		minm = fin[i]
	suffix.append(minm)
	i -= 1
suffix = suffix[::-1]
if k > 2:
	print(max(fin))
elif k == 2:
	i = 0
	maxm = -2 ** 30
	while i < len(fin) - 1:
		if max(prefix[i], suffix[i + 1]) > maxm:
			maxm = max(prefix[i], suffix[i + 1])
		i += 1
	print(maxm)
else:
	print(min(fin))


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


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


(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[len(a) - 1]))


def solve():
	segments = int(input().split()[1])
	arr = [int(s) for s in input().split()]
	if segments == 1:
		print(min(arr))
	elif segments == 2:
		print(max(arr[0], arr[-1]))
	else:
		print(max(arr))
solve()


import copy
(n, k) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
arr_copy = copy.deepcopy(arr)
arr.sort()
if k == 1:
	print(arr[0])
elif k >= 3:
	print(arr[-1])
else:
	print(max(arr_copy[0], arr_copy[-1]))


def fun(n, k, numbers):
	if k == 2:
		return max(numbers[0], numbers[len(numbers) - 1])
	if k > 2:
		return max(numbers)
	if k == 1:
		return min(numbers)
(var1, var2) = [int(x) for x in input().split()]
user_input = input().split(' ')
numbers = [int(x.strip()) for x in user_input]
print(fun(var1, var2, numbers))


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


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


(n, k) = 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]))


(n, k) = map(int, input().split())
l1 = 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) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if k == 1:
	print(min(a))
elif k == 2:
	ind = a.index(max(a))
	if ind == 0 or ind == n - 1:
		print(a[ind])
	else:
		print(max(a[0], a[n - 1]))
else:
	print(max(a))


[length, k] = [int(c) for c in input().split()]
array = [int(c) for c in input().split()]
if k == 1:
	print(min(array))
elif k == 2:
	best = -10 ** 9
	array1 = [array[0]]
	array2 = [array[-1]]
	for c in range(1, len(array)):
		array1.append(min(array1[c - 1], array[c]))
		array2.append(min(array1[c - 1], array[-c - 1]))
	for c in range(len(array1)):
		best = max(best, max(array1[c], array2[-c - 1]))
	print(best)
else:
	print(max(array))


[N, K] = map(int, input().split(' '))
nums = list(map(int, input().split(' ')))
if K == 1:
	print(min(nums))
elif K == 2:
	print(max(nums[0], nums[-1]))
else:
	print(max(nums))


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


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


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)


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


def readInts():
	return map(int, input().split())
(n, k) = readInts()
arr = list(readInts())
if k == 1:
	print(min(arr))
elif k == 2:
	A = [arr[i] for i in range(n)]
	for i in range(1, n):
		A[i] = min(A[i - 1], A[i])
	ans = min(arr)
	B = arr[n - 1]
	for i in range(n - 1, 0, -1):
		B = min(B, arr[i])
		ans = max(ans, max(A[i - 1], B))
	print(ans)
else:
	print(max(arr))


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


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


(n, k) = map(int, input().split())
array = list(map(int, input().split()))
if k == 1:
	print(min(array))
elif k == 2:
	prefix = []
	sufix = []
	for i in array:
		if not prefix:
			prefix.append(i)
		else:
			prefix.append(min(prefix[-1], i))
	for i in reversed(array):
		if not sufix:
			sufix.append(i)
		else:
			sufix.append(min(sufix[-1], i))
	sufix.reverse()
	res = -10000000000.0
	for i in range(n - 1):
		res = max(res, prefix[i], sufix[i + 1])
	print(res)
else:
	print(max(array))


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


def main():
	(n, k) = map(int, input().split())
	a = [int(c) for c in input().split()]
	if k == 2:
		print(max(a[0], a[-1]))
	else:
		print(max(a) if k >= 3 else min(a))
main()


nums = input().split()
nums = [int(x) for x in nums]
other_nums = input().split()
other_nums = [int(x) for x in other_nums]
if nums[1] == 1:
	print(min(other_nums))
elif nums[1] == 2:
	first = other_nums[0]
	last = other_nums[-1]
	if first < last:
		print(last)
	else:
		print(first)
elif nums[1] >= 3:
	print(max(other_nums))


def main():
	(n, k) = map(int, input().split())
	a = [int(elem) for elem in input().split()]
	if k == 1:
		print(min(a))
	elif k == 2:
		suf_min = [0] * n
		suf_min[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			suf_min[i] = min(a[i], suf_min[i + 1])
		pref_min = a[0]
		m = max(pref_min, suf_min[1])
		for i in range(1, n - 1):
			pref_min = min(pref_min, a[i])
			m = max(m, max(suf_min[i + 1], pref_min))
		print(m)
	else:
		print(max(a))
main()


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


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


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


from collections import deque
(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
if k == 1:
	print(min(nums))
elif k == 2:
	prefix = []
	postfix = deque()
	current = float('inf')
	for i in nums:
		current = min(i, current)
		prefix.append(current)
	current = float('inf')
	for i in range(len(nums) - 1, -1, -1):
		current = min(current, nums[i])
		postfix.appendleft(current)
	best = float('-inf')
	for i in range(len(nums)):
		best = max(best, max(prefix[i], postfix[i]))
	print(best)
else:
	print(max(nums))


(s, 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))


(ms, n) = map(int, input().split())
a = [int(i) for i in input().split()]
x = []
y = []
m = -100000000
p = 0
if n == 1:
	print(min(a))
elif n == 2:
	print(max(a[0], a[-1]))
else:
	print(max(a))


from collections import defaultdict, deque
from heapq import heappush, heappop

def solve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	prefix = [A[0]]
	suffix = [0] * n
	suffix[-1] = A[-1]
	for i in range(1, n):
		prefix.append(min(prefix[-1], A[i]))
	for i in range(n - 2, -1, -1):
		suffix[i] = min(suffix[i + 1], A[i])
	if k == 1:
		ans = min(A)
	elif k == 2:
		ans = float('-inf')
		for i in range(n - 1):
			ans = max(ans, max(prefix[i], suffix[i + 1]))
	else:
		ans = max(A)
	print(ans)
t = 1
while t:
	t -= 1
	solve()


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


R = lambda : list(map(int, input().split()))
(n, k) = R()
arr = R()
if k == 1:
	print(min(arr))
elif k >= 3:
	print(max(arr))
else:
	pre = [0] * n
	pre[0] = arr[0]
	suf = [0] * n
	suf[-1] = arr[-1]
	for i in range(1, n):
		pre[i] = min(pre[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		suf[i] = min(suf[i + 1], arr[i])
	ans = max(pre[0], suf[1])
	for i in range(1, n - 1):
		ans = max(ans, pre[i], suf[i + 1])
	print(ans)


(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:
	if max(a) == a[0] or max(a) == a[-1]:
		print(max(a))
		exit()
	if len(a) % 2 == 0:
		i = 0
		while i != len(a) // 2 - 1:
			if a[i] < a[len(a) - i - 1]:
				print(min(a[len(a) - i - 1:]))
				exit()
			elif a[i] > a[len(a) - i - 1]:
				if i == 0:
					print(a[0])
					exit()
				else:
					print(min(a[:i]))
					exit()
			else:
				i += 1
		print(min(a))
	else:
		i = 0
		while i != len(a) // 2:
			if a[i] < a[len(a) - i - 1]:
				print(min(a[len(a) - i - 1:]))
				exit()
			elif a[i] > a[len(a) - i - 1]:
				if i == 0:
					print(a[0])
					exit()
				else:
					print(min(a[:i]))
				exit()
			else:
				i += 1
		if a[len(a) // 2] <= min(a[:len(a) // 2]):
			print(min(a[len(a) // 2 + 1:]))
		else:
			print(min(a))


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) = map(int, input().split())
a = list(map(int, input().split()))
mx = a[0]
mxi = 0
for i in range(n):
	if a[i] >= mx:
		mx = a[i]
		mxi = i
if k >= 3:
	ans = mx
elif k == 2 and (mxi == n - 1 or mxi == 0):
	ans = mx
elif k == 1:
	ans = min(a)
else:
	ans = max(a[0], a[-1])
print(ans)


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


from sys import stdin, stdout

def solve():
	(num_elements, k) = [int(x) for x in stdin.readline().rstrip().split()]
	arr = [int(x) for x in stdin.readline().rstrip().split()]
	if k == 1:
		stdout.write(format('%d\n' % min(arr)))
	elif k == 2:
		stdout.write(format('%d\n' % max([arr[0], arr[num_elements - 1]])))
	else:
		stdout.write(format('%d\n' % max(arr)))
solve()
stdout.flush()


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


import sys
DEBUG = 0
if DEBUG:
	f = open('input.txt', 'r')
	input = f.readline
else:
	input = sys.stdin.readline

def main():
	INF = int(1000000000.0) + 2
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 1:
		print(min(a))
	elif k == 2:
		ans = 0
		min1 = a[0]
		for i in a:
			if i < min1:
				break
		ans = min1
		a.reverse()
		min1 = a[0]
		for i in a:
			if i < min1:
				break
		ans = max(ans, min1)
		print(ans)
	else:
		print(max(a))
main()


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


modulus = 10 ** 9 + 7

def main():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 1:
		print(min(arr))
	elif k == 2:
		minValue = 99999999999999
		maxValue = -99999999999999
		for i in range(len(arr) - 1):
			minValue = min(minValue, arr[i])
			maxValue = max(maxValue, minValue)
		minValue = 99999999999999
		for i in range(len(arr) - 1, 0, -1):
			minValue = min(minValue, arr[i])
			maxValue = max(maxValue, minValue)
		print(maxValue)
	else:
		print(max(arr))
main()


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


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l1 = l.copy()
l1.sort()
if k == 1:
	print(min(l))
elif k == 2:
	(a, b) = (10 ** 10, 10 ** 10)
	(c, d) = (-10 ** 10, -10 ** 10)
	for j in range(n):
		a = min(a, l[j])
		b = min(b, l[n - 1 - j])
		c = max(c, a)
		d = max(d, b)
	print(max(c, d))
else:
	print(max(l))


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
min_el = 10 ** 9 + 7
max_el = -min_el
for el in arr:
	if el < min_el:
		min_el = el
	if el > max_el:
		max_el = el
if k == 1:
	print(min_el)
elif k == 2:
	print(max(arr[0], arr[-1]))
else:
	print(max_el)


(a, b) = tuple(map(int, input().split()))
nums = list(map(int, input().split()))
sorted_nums = nums.copy()
sorted_nums.sort()
if b == 1:
	print(sorted_nums[0])
elif b == 2:
	for i in range(1, a + 1):
		if sorted_nums[-i] == nums[0] or sorted_nums[-i] == nums[-1]:
			print(sorted_nums[-i])
			break
		else:
			continue
else:
	print(sorted_nums[-1])


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


(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) = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
	print(min(a))
elif k > 2:
	print(max(a))
else:
	suf = [0] * (n + 1)
	suf[n - 1] = a[n - 1]
	i = n - 2
	while i >= 0:
		suf[i] = min(a[i], suf[i + 1])
		i -= 1
	pre = a[0]
	ans = max(pre, suf[1])
	for i in range(1, n - 1):
		pre = min(pre, a[i])
		ans = max(ans, max(suf[i + 1], pre))
	print(ans)


from sys import stdin
inp = list(map(lambda s: s.strip(), stdin.readlines()))
(_n, k) = map(int, inp[0].split())
l = list(map(int, inp[1].split()))
if k is 1:
	print(min(l))
elif k is 2:
	print(max(l[0], l[-1]))
else:
	print(max(l))


import sys
nk = sys.stdin.readline()
fline = nk.split()
fline[0].strip()
fline[1].strip()
fline = list(map(int, fline))
k = fline[1]
a = sys.stdin.readline()
arr = a.split()
for item in arr:
	item.strip()
arr = list(map(int, arr))
first = arr[0]
last = arr[-1]
arr.sort()
if k == 1:
	print('{}'.format(int(arr[0])))
elif k > 2:
	print('{}'.format(int(arr[-1])))
else:
	print('{}'.format(int(max(first, last))))


def maxMaxMin(nums, k):
	if k == 1:
		return min(nums)
	else:
		maximum = max(nums)
		if k != 2:
			return maximum
		if nums[0] == maximum or nums[-1] == maximum:
			return maximum
		return max(nums[0], nums[-1])
(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
print(maxMaxMin(nums, k))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
	print(min(a))
elif k == 2:
	(l, r) = ([a[0]] + [0] * (n - 1), [0] * (n - 1) + [a[-1]])
	for i in range(1, n):
		l[i] = min(l[i - 1], a[i])
		r[n - i - 1] = min(r[n - i], a[n - i - 1])
	print(max((max(l[i], r[i + 1]) for i in range(n - 1))))
else:
	print(max(a))


from sys import stdin as fin
(n, k) = map(int, fin.readline().split())
arr = list(map(int, fin.readline().split()))
if k >= 3:
	print(max(arr))
elif k == 1:
	print(min(arr))
else:
	print(max(arr[0], arr[-1]))


(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:
	prefix = [None] * n
	suffix = [None] * n
	for i in range(n):
		if i == 0:
			prefix[i] = a[i]
		else:
			prefix[i] = min(prefix[i - 1], a[i])
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			suffix[i] = a[i]
		else:
			suffix[i] = min(suffix[i + 1], a[i])
	ans = -10 ** 9 - 7
	for d in range(n - 1):
		ans = max(ans, prefix[d], suffix[d + 1])
	print(ans)


(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 and a.index(max(a)) in [0, n - 1] or k >= 3:
	print(max(a))
else:
	a1 = a[::-1]
	pref = [a[0]]
	pref1 = [a1[0]]
	for i in range(1, n):
		pref.append(min(pref[i - 1], a[i]))
		pref1.append(min(pref1[i - 1], a1[i]))
	ans = -10000000000
	for i in range(n - 1):
		ans = max(ans, max(pref[i], pref1[n - i - 2]))
	print(ans)


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


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


(a, b) = map(int, input().split())
if b == 1:
	print(min(list(map(int, input().split()))))
elif b > 2:
	print(max(list(map(int, input().split()))))
else:
	z = list(map(int, input().split()))
	pre = [z[0]]
	for i in range(1, a):
		pre += [min(pre[-1], z[i])]
	suff = [10000000000] * a
	suff[-1] = z[-1]
	for i in range(a - 2, -1, -1):
		suff[i] = min(suff[i + 1], z[i])
	ans = -pow(10, 10)
	for i in range(0, a - 1):
		ans = max(ans, pre[i], suff[i + 1])
	print(ans)


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


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


(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:
	min_pref = [0 for i in range(n - 1)]
	min_suff = [0 for i in range(n)]
	min_pref[0] = a[0]
	for i in range(1, n - 1):
		if a[i] < min_pref[i - 1]:
			min_pref[i] = a[i]
		else:
			min_pref[i] = min_pref[i - 1]
	min_suff[n - 1] = a[n - 1]
	for i in range(n - 2, 0, -1):
		if a[i] < min_suff[i + 1]:
			min_suff[i] = a[i]
		else:
			min_suff[i] = min_suff[i + 1]
	ans = -100000000000
	for i in range(n - 1):
		if max(min_pref[i], min_suff[i + 1]) > ans:
			ans = max(min_pref[i], min_suff[i + 1])
	print(ans)


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


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


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


from collections import deque as de
import math
from collections import Counter as cnt
from functools import reduce
from typing import MutableMapping

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic

def Log2(x):
	return math.log10(x) / math.log10(2)

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
	print(min(a))
elif k > 2:
	print(max(a))
else:
	print(max(a[0], a[n - 1]))


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


first_line = input().split(' ')
array_size = int(first_line[0])
subsegments = int(first_line[1])
array = input().split(' ')
desired_array = [int(numeric_string) for numeric_string in array]
int_array = [int(numeric_string) for numeric_string in array]
desired_array.sort(reverse=True)
if subsegments == 1:
	print(desired_array[-1])
elif subsegments >= 3:
	print(desired_array[0])
elif int_array[0] > int_array[-1]:
	print(int_array[0])
else:
	print(int_array[-1])


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


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


import sys

def ria():
	return [int(x) for x in input().split()]
(n, k) = (int(x) for x in input().split())
a = ria()
if k == 1:
	ans = min(a)
if k == 2:
	minn1 = min(a[1:n])
	maks1 = max(a[0], minn1)
	minn2 = min(a[0:n - 1])
	maks2 = max(minn2, a[n - 1])
	ans = max(maks1, maks2)
if k > 2:
	ans = max(a)
print(ans)


(s1, s2) = map(int, input().split())
result = list(map(int, input().split()))
if s2 == 1:
	print(min(result))
elif s2 == 2:
	print(max(result[0], result[-1]))
else:
	print(max(result))


(n, k) = map(int, input().split())
seps = k - 1
arr = [int(x) for x in input().split()]
smallest = min(arr)
biggest = max(arr)
if seps == 0:
	print(smallest)
elif seps == 1:
	print(arr[0] if arr[0] > arr[len(arr) - 1] else arr[len(arr) - 1])
else:
	print(biggest)


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


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


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


from math import ceil
(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))


(b, b) = input().split()
a = input().split()
for i in range(len(a)):
	a[i] = int(a[i])
b = int(b)
if b == 1:
	a.sort()
	print(a[0])
elif b == 2:
	k = a[:]
	c = []
	k.sort()
	if k[len(k) - 1] == a[0]:
		print(a[0])
	elif k[len(k) - 1] == a[len(a) - 1]:
		print(a[len(a) - 1])
	else:
		c.append(k[0])
		c.append(k[1])
		c.append(a[0])
		c.append(a[len(a) - 1])
		c.sort()
		print(c[len(c) - 1])
elif b >= 3:
	a.sort()
	print(a[len(a) - 1])


(a, b) = map(int, input().split(' '))
m1 = list(map(int, input().split(' ')))
m = sorted(m1)
if b == 1:
	print(m[0])
elif b == 2:
	print(max(m1[-1], m1[0]))
else:
	print(m[-1])


(n, k) = input().split()
a = list(map(int, input().split()))
n = int(n)
k = int(k)
if k == 1:
	print(min(a))
elif k == 2:
	L = [0] * n
	L[0] = a[0]
	m = a[0]
	for i in range(1, n):
		if a[i] < m:
			m = a[i]
		L[i] = m
	R = [0] * n
	m = a[n - 1]
	R[n - 1] = m
	for i in range(n - 2, -1, -1):
		if a[i] < m:
			m = a[i]
		R[i] = m
	ans = -float('inf')
	for i in range(0, n):
		if ans < max(L[i], R[n - 1 - i]):
			ans = max(L[i], R[n - 1 - i])
	print(ans)
else:
	print(max(a))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mx = a.index(max(a))
nk = n - k
RL = []
if mx - nk < 0:
	st = 0
else:
	st = mx - nk
if mx + nk > n - 1:
	en = n - 1
else:
	en = mx + nk
if k == 1:
	print(min(a))
elif k == 2:
	print(max(a[0], a[n - 1]))
else:
	for i in range(st, mx + 1):
		RL.append(a[i])
	for j in range(mx, en + 1):
		RL.append(a[j])
	print(max(RL))