codeforces 872 B. Maximum of Maximums of Minimums

codeforces 872 B. Maximum of Maximums of Minimums

​​ 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#include#define N 110000using namespace std;int n,k,a[N];int main(){// freopen("cf.in","r",stdin); scanf("%d%d",&n,&k); for (int i=1;i<=n;++i) scanf("%d",&a[i]);if (k==2){ printf("%d",max(a[1],a[n]));return 0; } sort(a+1,a+n+1); if (k<2) {printf("%d",a[1]);return 0;} if (k>=3) {printf("%d",a[n]);return 0;} return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。