CF870B.Maximum of Maximums of Minimums

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given an array a1,a2,...,ana_{1},a_{2},...,a_{n} consisting of nn integers, and an integer kk . You have to split the array into exactly kk non-empty subsegments. You'll then compute the minimum integer on each subsegment, and take the maximum integer over the kk 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 nn and kk ( 1<=k<=n<=1051<=k<=n<=10^{5} ) — the size of the array aa and the number of subsegments you have to split the array to.

The second line contains nn integers a1,a2,...,ana_{1},a_{2},...,a_{n} ( 109<=ai<=109-10^{9}<=a_{i}<=10^{9} ).

输出格式

Print single integer — the maximum possible integer you can get if you split the array into kk non-empty subsegments and take maximum of minimums on the subsegments.

输入输出样例

  • 输入#1

    5 2
    1 2 3 4 5
    

    输出#1

    5
    
  • 输入#2

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

    输出#2

    -5
    

说明/提示

A subsegment [l,r][l,r] ( l<=rl<=r ) of array aa is the sequence al,al+1,...,ara_{l},a_{l+1},...,a_{r} .

Splitting of array aa of nn elements into kk subsegments [l1,r1][l_{1},r_{1}] , [l2,r2][l_{2},r_{2}] , ..., [lk,rk][l_{k},r_{k}] ( l1=1l_{1}=1 , rk=nr_{k}=n , li=ri1+1l_{i}=r_{i-1}+1 for all i>1i>1 ) is kk sequences (al1,...,ar1),...,(alk,...,ark)(a_{l1},...,a_{r1}),...,(a_{lk},...,a_{rk}) .

In the first example you should split the array into subsegments [1,4][1,4] and [5,5][5,5] that results in sequences (1,2,3,4)(1,2,3,4) and (5)(5) . The minimums are min(1,2,3,4)=1min(1,2,3,4)=1 and min(5)=5min(5)=5 . The resulting maximum is max(1,5)=5max(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][1,5] , that results in one sequence (4,5,3,2,1)(-4,-5,-3,-2,-1) . The only minimum is min(4,5,3,2,1)=5min(-4,-5,-3,-2,-1)=-5 . The resulting maximum is 5-5 .

首页