4266. [THUPC 2025 pre] Harmful Machine Learning

【题目描述】

人工智能领域大神 The NIT 正在训练机器人 The BOT。

The BOT 在一个 $1\times n$ 的网格上移动，其中在 $(1,i)$ 上有数字 $a_i$。The BOT 初始在格子 $(1,x)$, The BOT 想要走到一个数字尽量大的格子。每一步 The BOT 可以选择移动到相邻的一个格子或是不动，并且在移动后可以选择是否选择格子上的数字并结束游戏，而为了训练 The BOT 的能力，The NIT 会给出一些阻碍，在 The BOT 选择是否结束之后，The NIT 可以将两个数字交换位置。

具体地说，我们可以把整个游戏看成若干个回合，初始 The BOT 在位置 $(1,x)$，在一个回合中，以下事件会按顺序依次发生：

1. The NIT 选择两个位置 $1\leq i,j\leq n$，并交换 $a_i,a_j$ 的值，注意 $i$ 可以等于 $j$，此时交换不会带来任何变化。
2. The BOT 选择移动到一个相邻的位置或是原地不动，令 The BOT 现在所在的位置为 $y$，即选择 $1\leq z\leq n$ 且 $|z-y|\leq 1$，并移动到 $(1,z)$。
3. The BOT 选择是否结束游戏，令 The BOT 现在所在的位置为 $y$，如果选择结束则会获得 $a_y$ 的分数并立刻结束游戏，否则无事发生。

可以发现，如果 The BOT 一直不选择结束游戏，则游戏永远不会结束，为了防止这个情况的发生，在游戏的第 $10^{114514}$ 个回合，The BOT 必须选择立刻结束游戏。

The NIT 希望 The BOT 结束游戏时的分数最小，而 The BOT 希望这个分数最大。The NIT 和 The BOT 都是绝顶聪明的，但他们并没有时间玩 $10^{114514}$ 个回合，于是他们请你帮他们计算一下，The BOT 最终的分数是多少？

【输入格式】

本题含有多组测试数据。

第一行一个整数 $T(1\leq T\leq 10^5)$，表示测试数据数量。

对于每一组数据：

第一行两个正整数 $n,x(1\leq n\leq 10^5,1\leq x\leq n)$，分别表示网格的长度以及初始位置 $(1,x)$。

之后一行 $n$ 个非负整数 $a_i(0\leq a_i\leq 10^9)$。

保证所有数据的 $n$ 的总和不超过 $5\times 10^5$。

【输出格式】

对于每一组数据，输出一行一个数表示答案。

【样例输入】

4
3 2
1 2 3
13 4
1 1 4 5 1 4 1 9 1 9 8 1 0
4 2
1 10 100 1000
1 1
114514

【样例输出】

3
4
100
114514

【来源】

清华大学学生算法协会 GitLink 仓库