P13091 [FJCPC 2025] 中位数

CFJ 拥有一个长度为 $n$ 的数组 $a$，且 $n$ 必定为奇数。 由于 CFJ 十分喜爱中位数，他将进行以下操作：每次选择数组中连续的三个数字，并将它们合并为其中位数，替换这三个数字。具体而言，每次选择任意一个位置 $i$（满足 $1 < i < n$），删除 $a_{i-1}$、$a_i$ 和 $a_{i+1}$，并在该位置插入这三个数字的中位数。 CFJ 将持续进行上述操作，直到数组中仅剩一个数字为止。整个过程共需进行 $\frac{n-1}{2}$ 次合并。他期望这个最终剩余的数字尽可能大。你的任务是帮助 CFJ 确定这个数字的最大可能值。 **中位数的定义为：将一组长度为 $n$ 的数组从小到大排序后，排名第$\lfloor \frac{n+1}{2} \rfloor$小的数字。**

**本题包含多组测试数据。** 第一行，包含一个整数 $T$（$1\le T \le 10^6$），表示测试数据的组数。 对于每组数据： 第一行，包含一个整数 $n$（$1\le n< 10^5$），且 $n$ 必定为奇数。 第二行，包含 $n$ 个整数 $a_1,a_2,\cdots, a_n$（$1\le a_i\le 10^9$）。 数据保证 $\sum n \leq 10^6$。

对于每个测试用例，输出 $\frac{n-1}{2}$ 次合并以后剩下数字的最大值。

对于第四个样例而言，数组 $ A = [ \ 1 \ 2 \ 3 \ 5 \ 6 \ 7 \ 4 \ ] $ 一种可行的方案是：$ [ \ \underline{1 \ 2 \ 3} \ 5 \ 6 \ 7 \ 4 \ ] \rightarrow [ \ \underline{2 \ 5 \ 6} \ 7 \ 4 \ ] \rightarrow [ \ \underline{5 \ 7 \ 4} \ ] \rightarrow [ \ 5 \ ]$。 其中 $ \underline{a_{i-1} \ a_i \ a_{i+1}} $ 下划线选择的连续三个数字表示每次操作合并的对象。