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

Вы и ваш $$$n - 1$$$ друг нашли массив целых чисел $$$a_1, a_2, \dots, a_n$$$. Вы решили разделить его следующим образом: все $$$n$$$ человек встают в линию в определенном порядке. Каждую минуту, человек в начале линии выбирает либо первый, либо последний элемент массива, удаляет его и забирает себе. Затем, он выходит из линии и процесс продолжается со следующим стоящим в линии человеком.

Вы стоите на $$$m$$$-й позиции в линии. Перед тем, как процесс начнется, вы можете выбрать не больше чем $$$k$$$ различных людей в линии и каждого из них убедить всегда брать либо первый, либо последний элемент массива во время их хода (для каждого человека свой выбор, не обязательно у всех одинаковый), не зависимо от того, какие это элементы. После того, как процесс начнется, вы не сможете убедить больше людей или изменить выбор уже убежденных вами людей.

Предположим, что вы сделаете ваш выбор оптимально. Чему равно максимальное целое число $$$x$$$, такое что, вне зависимости от ходов тех друзей, которых вы не выбрали, чтобы убедить, элемент массива, который вы получите на вашем ходу, будет не меньше, чем $$$x$$$?

Обратите внимание, что друзья, которых вы не выбрали для того, чтобы убедить сделать их заранее определенный вами выбор, могут делать свой выбор произвольно и они не обязательно будут брать наибольший доступный для них элемент.

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

Входные данные содержат несколько тестовых случаев. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$)  — количество тестовых случаев. В следующих строках находится их описание.

В первой строке описания каждого тестового случая находятся три разделенных пробелом целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le m \le n \le 3500$$$, $$$0 \le k \le n - 1$$$)  — количество элементов в массиве, ваша позиция в линии и количество человек, чей выбор вы можете зафиксировать.

Во второй строке описания каждого тестового случая содержится $$$n$$$ положительных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)  — элементы массива.

Гарантируется, что сумма значений $$$n$$$ по всем тестовым случаям не превосходит $$$3500$$$.

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

Для каждого тестового случая, выведите наибольшее целое число $$$x$$$, такое что вы можете гарантировать себе получить число не меньше, чем $$$x$$$.

Пример
Входные данные
4
6 4 2
2 9 2 3 8 5
4 4 1
2 13 60 4
4 1 3
1 2 2 1
2 2 0
1 2
Выходные данные
8
4
1
1
Примечание

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

  • первый человек возьмет последний элемент ($$$5$$$), потому что он или она были убеждены вами взять последний элемент. После этого хода оставшийся массив будет $$$[2, 9, 2, 3, 8]$$$;
  • второй человек возьмет первый элемент ($$$2$$$), потому что он или она были убеждены вами взять первый элемент. После этого хода оставшийся массив будет $$$[9, 2, 3, 8]$$$;
  • если третий человек выберет взять первый элемент ($$$9$$$), к вашему ходу оставшийся массив будет $$$[2, 3, 8]$$$ и вы сможете взять $$$8$$$ (последний элемент);
  • если третий человек выберет взять последний элемент ($$$8$$$), к вашему ходу оставшийся массив будет $$$[9, 2, 3]$$$ и вы сможете взять $$$9$$$ (первый элемент).

Таким образом, эта стратегия гарантирует получить в конце число не меньше, чем $$$8$$$. Можно доказать, что не существует стратегии, гарантирующей получить число не меньше чем $$$9$$$. Таким образом, ответ равен $$$8$$$.

Во втором тестовом случае, одной из оптимальных стратегий является убедить первого человека взять первый элемент. Тогда, в худшем случае второй и третий человек возьмут первый элементы и вы получите число $$$4$$$.