Дан массив 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.
| Технокубок 2018 - Отборочный Раунд 2 |
|---|
| Закончено |
