As an experiment the Educational Codeforces Round 33 will be rated for Div. 2.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Maximum of Maximums of Minimums

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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*_{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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/23/2017 06:44:22 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|