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