题目描述

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}$ 次合并以后剩下数字的最大值。

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 \ ]$ 一种可行的方案是：$ [ \ \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}}$ 下划线选择的连续三个数字表示每次操作合并的对象。