870B.md (2299B)
1 Source: https://codeforces.com/problemset/problem/870/B 2 3 B. Maximum of Maximums of Minimums 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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? 22 23 Definitions of subsegment and array splitting are given in notes. 24 25 Input 26 27 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. 28 29 The second line contains *n* integers *a*1, *a*2, ..., *a**n* ( - 109 ≤ *a**i* ≤ 109). 30 31 Output 32 33 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. 34 35 Examples 36 37 Input 38 39 ``` 40 5 2 41 1 2 3 4 5 42 ``` 43 44 Output 45 46 ``` 47 5 48 ``` 49 50 Input 51 52 ``` 53 5 1 54 -4 -5 -3 -2 -1 55 ``` 56 57 Output 58 59 ``` 60 -5 61 ``` 62 63 Note 64 65 A subsegment [*l*, *r*] (*l* ≤ *r*) of array *a* is the sequence *a**l*, *a**l* + 1, ..., *a**r*. 66 67 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*). 68 69 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. 70 71 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.