У Ashish есть массив \(a\) размера \(n\).
Подпоследовательность массива \(a\) определяется, как последовательность, которая может быть получена из \(a\) с помощью удаления некоторых элементов (возможно нуля) без изменения порядка оставшихся элементов.
Рассмотрим подпоследовательность \(s\) массива \(a\). Он определяет цену подпоследовательности \(s\) как минимум между:
- Максимумом по всем числам, стоящим на нечетных позициях в \(s\).
- Максимумом по всем числам, стоящим на четных позициях в \(s\).
Обратите внимание, что индекс числа определяется, как его индекс в \(s\), независимо от его индекса в \(a\). Все позиции нумеруются с \(1\). Другими словами, цена \(s\) равна \(min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))\).
Например, цена последовательности \(\{7, 5, 6\}\) равна \(min( max(7, 6), max(5) ) = min(7, 5) = 5\).
Помогите ему найти минимальную цену какой-то подпоследовательности размера \(k\).
Примечание
В первом тесте, рассмотрим подпоследовательность \(s\) = \(\{1, 3\}\). Здесь цена подпоследовательности равна \(min(max(1), max(3)) = 1\).
Во втором тесте, рассмотрим подпоследовательность \(s\) = \(\{1, 2, 4\}\). Здесь цена подпоследовательности равна \(min(max(1, 4), max(2)) = 2\).
В четвертом тесте, рассмотрим подпоследовательность \(s\) = \(\{3, 50, 2, 4\}\). Здесь цена подпоследовательности равна \(min(max(3, 2), max(50, 4)) = 3\).