Intermediário Informática Semana 35

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

Entrada Saída
5 2

1 2 3 4 5

5
5 1

-4 -5 -3 -2 -1

-5