Máximo de máximo de mínimos

É dado um vetor $a_1,a_2,...,a_n$ que consiste de $n$ inteiros, e um inteiro $k$. Você tem que dividir o vetor em extamente $k$ subsegmentos não vazios. Depois disso computar o inteiro mínimo em cada subsegmento, e tirar o máximo sobre os $k$ mínimos. Qual éo valor máximo que se pode obter?

Entrada

A primeira linha contém dois inteiros $n$ e $k$, $(1 \leq k \leq n \leq 10^5)$ – o tamanho do vetor $a$ e o número de subsegmentos em que você deve o dividir.

A segunda linha contém $n$ inteiros $a_1, a_2, ..., a_n\ (-10^9 \leq a_i \leq 10^9)$.

Saída

Um único inteiro – o valor máximo que se pode obter caso se divida o vetor em $k$ subsegmentos não vazios,  e se tire o máximo do mínimo dos subsegmentos.

Nota

Um subsegmento do vetor $a$ é a uma sequência $[l,r], (l \leq r)$, $a_l, a_{l+1},...,a_r$.

Exemplos