Mind Control

题意翻译

你和$n-1$个朋友发现了一个含有$n$个整数的数组，$n$个人排队依次取走数组的第一个元素或最后一个元素（类似于双端队列）。你是队伍中的第$m$个人，在**所有人开始取数字前**你可以指定队伍中不同的$k$个人，使他们在取的时候听从你的指挥。一旦第一个人开始取数字，你就不能再指挥其他人或改变你之前的命令了。 求最大的整数$X$使得**无论未经你控制的人如何选择**，你能取到的数都**不小于**$X$。 ## 输入： 第一行$1$个整数$t$表示测试数据的组数，接下来$t$组数据，每组两行，第一行三个整数$n$,$m$,$k$$(1\le m\le n\le3500,0 \le k \le n-1)$，第二行$n$个整数表示数组中的$n$个元素$(1\le a_i\le10^9)$。 ## 输出： 一个整数$X$，每组数据单独一行。

题目描述

You and your $ n - 1 $ friends have found an array of integers $ a_1, a_2, \dots, a_n $ . You have decided to share it in the following way: All $ n $ of you stand in a line in a particular order. Each minute, the person at the front of the line chooses either the first or the last element of the array, removes it, and keeps it for himself. He then gets out of line, and the next person in line continues the process. You are standing in the $ m $ -th position in the line. Before the process starts, you may choose up to $ k $ different people in the line, and persuade them to always take either the first or the last element in the array on their turn (for each person his own choice, not necessarily equal for all people), no matter what the elements themselves are. Once the process starts, you cannot persuade any more people, and you cannot change the choices for the people you already persuaded. Suppose that you're doing your choices optimally. What is the greatest integer $ x $ such that, no matter what are the choices of the friends you didn't choose to control, the element you will take from the array will be greater than or equal to $ x $ ? Please note that the friends you don't control may do their choice arbitrarily, and they will not necessarily take the biggest element available.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains three space-separated integers $ n $ , $ m $ and $ k $ ( $ 1 \le m \le n \le 3500 $ , $ 0 \le k \le n - 1 $ ) — the number of elements in the array, your position in line and the number of people whose choices you can fix. The second line of each test case contains $ n $ positive integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3500 $ .

输出格式

For each test case, print the largest integer $ x $ such that you can guarantee to obtain at least $ x $ .

输入输出样例

输入样例 #1

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

输出样例 #1

8
4
1
1

说明

In the first test case, an optimal strategy is to force the first person to take the last element and the second person to take the first element. - the first person will take the last element ( $ 5 $ ) because he or she was forced by you to take the last element. After this turn the remaining array will be $ [2, 9, 2, 3, 8] $ ; - the second person will take the first element ( $ 2 $ ) because he or she was forced by you to take the first element. After this turn the remaining array will be $ [9, 2, 3, 8] $ ; - if the third person will choose to take the first element ( $ 9 $ ), at your turn the remaining array will be $ [2, 3, 8] $ and you will take $ 8 $ (the last element); - if the third person will choose to take the last element ( $ 8 $ ), at your turn the remaining array will be $ [9, 2, 3] $ and you will take $ 9 $ (the first element). Thus, this strategy guarantees to end up with at least $ 8 $ . We can prove that there is no strategy that guarantees to end up with at least $ 9 $ . Hence, the answer is $ 8 $ . In the second test case, an optimal strategy is to force the first person to take the first element. Then, in the worst case, both the second and the third person will take the first element: you will end up with $ 4 $ .

题意翻译

你和$n-1$个朋友发现了一个含有$n$个整数的数组，$n$个人排队依次取走数组的第一个元素或最后一个元素（类似于双端队列）。你是队伍中的第$m$个人，在**所有人开始取数字前**你可以指定队伍中不同的$k$个人，使他们在取的时候听从你的指挥。一旦第一个人开始取数字，你就不能再指挥其他人或改变你之前的命令了。 求最大的整数$X$使得**无论未经你控制的人如何选择**，你能取到的数都**不小于**$X$。 ## 输入： 第一行$1$个整数$t$表示测试数据的组数，接下来$t$组数据，每组两行，第一行三个整数$n$,$m$,$k$$(1\le m\le n\le3500,0 \le k \le n-1)$，第二行$n$个整数表示数组中的$n$个元素$(1\le a_i\le10^9)$。 ## 输出： 一个整数$X$，每组数据单独一行。