Maximum of Maximums of Minimums

题目描述 给你一个数组 a1,a2...an，还有一个整数n和整数k。 你必须把这堆数组恰好分成k个非空数组。然后，计算每个子数组上对最小整数，并取k个最小值中的最大整数。 你能得到最大的整数是什么？ 子数组和分开数组的定义在说明给出。 输入格式 第一行 n,k (1 <= k <= n <= 1e+5 ) (n是数组长度，k是分成的子数组数) 第二行包括n个整数 a1,a2,a3...an (-1e+9 <= ax <= 1e+9) 输出格数 输出一个整数，表示可以获得的最大整数，如果将原数组拆成k个非空子数组。 说明 一个数组a的子数组[l,r] 是 al,al+1,...ar 将数组分成k个子数组[l1,r1],[l2,r2]...[lk,rk] (l1 = 1, rk = n, li = ri+1) 一共k个子数组（意思就是切成了k个小数组） 在第一个样例中，你应该将数列分割为数组【1,2,3,4]和5的数组,表示[1,4] 和[5,5]。最小值为min(5)=1，min（5）=5、结果的最大值max(1,5) = 5。显然易见地，这是最佳答案。 在第二个样例中，你唯一的选择就是把这个数组分成(-4 -5 -3 -2 -1)的一个子数组[1，5]。唯一的最小值为min(-4,-5,-3,-2,-1)=-5，最小值的结果是-5。 感谢@Himself65 @paizhang 提供的翻译

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.

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} $ ).

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.

5 2
1 2 3 4 5

5

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

-5

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_{l1},...,a_{r1}),...,(a_{lk},...,a_{rk}) $ . 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 $ .