您和您的 $$$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$$$。
示例
输入 #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
注意
在第一个测试用例中,最佳策略是强制第一个人获取最后一个元素,第二个人获取第一个元素。
- 第一个人将采取最后一个元素($$$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$$$。