#P13091. [FJCPC 2025] 中位数

[FJCPC 2025] 中位数

题目描述

CFJ 拥有一个长度为 nn 的数组 aa,且 nn 必定为奇数。

由于 CFJ 十分喜爱中位数,他将进行以下操作:每次选择数组中连续的三个数字,并将它们合并为其中位数,替换这三个数字。具体而言,每次选择任意一个位置 ii(满足 1<i<n1 < i < n),删除 ai1a_{i-1}aia_iai+1a_{i+1},并在该位置插入这三个数字的中位数。

CFJ 将持续进行上述操作,直到数组中仅剩一个数字为止。整个过程共需进行 n12\frac{n-1}{2} 次合并。他期望这个最终剩余的数字尽可能大。你的任务是帮助 CFJ 确定这个数字的最大可能值。

中位数的定义为:将一组长度为 nn 的数组从小到大排序后,排名第n+12\lfloor \frac{n+1}{2} \rfloor小的数字。

输入格式

本题包含多组测试数据。

第一行,包含一个整数 TT1T1061\le T \le 10^6),表示测试数据的组数。

对于每组数据:

第一行,包含一个整数 nn1n<1051\le n< 10^5),且 nn 必定为奇数。

第二行,包含 nn 个整数 a1,a2,,ana_1,a_2,\cdots, a_n1ai1091\le a_i\le 10^9)。

数据保证 n106\sum n \leq 10^6

输出格式

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

6
1
1
3
1 2 2
5
1 3 4 5 2
7
1 2 3 5 6 7 4
9
9 9 8 2 4 4 3 5 3
9
4 4 9 2 9 5 8 3 3
1 
2 
3 
5 
9 
4

提示

对于第四个样例而言,数组 A=[ 1 2 3 5 6 7 4 ] 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 \ ]$。

其中 ai1 ai ai+1 \underline{a_{i-1} \ a_i \ a_{i+1}} 下划线选择的连续三个数字表示每次操作合并的对象。