B. Максимум максимума из минимумов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив a1, a2, ..., an из n чисел, а также число k. Массив нужно разбить на ровно k непустых подотрезков. На каждом подотрезке вычисляется минимум, а из полученных k минимумов берется максимум. А какое максимальное число можно таким образом получить?

Определения подотрезка и разбиения массива на подотрезки находятся в примечаниях.

Входные данные

В первой строке записаны через пробел два целых числа n и k (1 ≤ k ≤ n ≤  105) — размер массива a и количество подотрезков, на которые нужно разбить массив.

Во второй строке записано n целых чисел через пробел: a1,  a2,  ...,  an ( - 109  ≤  ai ≤  109).

Выходные данные

Выведите единственное число — максимальный максимум, который можно получить, разбив данный массив на k подотрезков и взяв максимум из минимумов на этих подотрезках.

Примеры
Входные данные
5 2
1 2 3 4 5
Выходные данные
5
Входные данные
5 1
-4 -5 -3 -2 -1
Выходные данные
-5
Примечание

Подотрезок [l,  r] (l ≤ r) массива a — это последовательность al,  al + 1,  ...,  ar.

Разбиение массива a из n элементов на k подотрезков, [l1, r1], [l2, r2], ..., [lk, rk] (l1 = 1, rk = n, li = ri - 1 + 1 при 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.