Maximum of Maximums of Minimums

n개의 정수로 이루어진 배열 a1, a2, ..., an과 정수 k가 주어진다. 배열을 정확히 k개의 비어 있지 않은 부분 구간으로 나누어야 한다. 그런 다음 각 부분 구간에서 최솟값을 구하고, 이렇게 얻은 k개의 최솟값 중 최댓값을 취한다. 얻을 수 있는 정수의 가능한 최댓값은 얼마인가?

부분 구간과 배열 분할의 정의는 참고에 주어진다.

첫째 줄에 두 정수 n와 k (1 ≤ k ≤ n ≤ 105) — 배열 a의 크기와 배열을 나누어야 하는 부분 구간의 수가 주어진다.

둘째 줄에 n개의 정수 a1, a2, ..., an ( - 109 ≤ ai ≤ 109)이 주어진다.

배열을 k개의 비어 있지 않은 부분 구간으로 나누고 각 부분 구간의 최솟값 중 최댓값을 취할 때 얻을 수 있는 정수의 가능한 최댓값 하나를 출력한다.

배열 a의 부분 구간 [l, r] (l ≤ r)은 수열 al, al + 1, ..., ar이다.

n개의 원소로 이루어진 배열 a를 k개의 부분 구간 $[l1, r1]$, $[l2, r2]$, ..., [lk, rk] (l1 = 1, rk = n, li = ri - 1 + 1 for all i > 1)으로 나눈 것은 k개의 수열 (al1, ..., ar1), ..., (alk, ..., ark)이다.

첫 번째 예제에서는 배열을 부분 구간 $[1, 4]$와 $[5, 5]$로 나누어 수열 (1, 2, 3, 4)와 (5)를 얻어야 한다. 최솟값은 min(1, 2, 3, 4) = 1과 min(5) = 5이다. 그 결과의 최댓값은 max(1, 5) = 5이다. 이보다 큰 결과를 얻을 수 없음은 명백하다.

두 번째 예제에서 가능한 유일한 방법은 배열을 하나의 부분 구간 $[1, 5]$로 나누어 하나의 수열 ( - 4, - 5, - 3, - 2, - 1)을 얻는 것이다. 유일한 최솟값은 min( - 4, - 5, - 3, - 2, - 1) = - 5이다. 그 결과의 최댓값은 - 5이다.