题目描述

Pak Chanek 有一个包含 $n$ 个正整数的数组 $a$。由于他正在学习如何计算两个数的向下取整平均值，他想在他的数组 $a$ 上练习这个操作。

只要数组 $a$ 中至少有两个元素，Pak Chanek 就会进行如下三步操作：

1. 选择两个不同的下标 $i$ 和 $j$（$1 \leq i, j \leq |a|$，$i \neq j$），其中 $|a|$ 表示当前数组 $a$ 的长度。
2. 将 $\lfloor \frac{a_i+a_j}{2} \rfloor$ $^{\text{∗}}$ 添加到数组末尾。
3. 从数组中移除 $a_i$ 和 $a_j$，并将剩余部分拼接成新的数组。

例如，假设 $a=[5,4,3,2,1,1]$。如果选择 $i=1$ 和 $j=5$，则操作后数组变为 $a=[4,3,2,1,3]$。如果选择 $i=4$ 和 $j=3$，则操作后数组变为 $a=[5,4,1,1,2]$。

经过所有操作后，数组中只剩下一个元素 $x$。请你求出如果 Pak Chanek 最优地进行操作，最终 $x$ 的最大可能值是多少。

$^{\text{∗}}$ $\lfloor x \rfloor$ 表示 $x$ 的向下取整函数，即不大于 $x$ 的最大整数。例如，$\lfloor 6 \rfloor = 6$，$\lfloor 2.5 \rfloor=2$，$\lfloor -3.6 \rfloor=-4$，$\lfloor \pi \rfloor=3$。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试数据组数。

每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 50$），表示数组 $a$ 的长度。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

注意，所有测试数据中 $n$ 的总和没有上界。

输出格式

对于每组测试数据，输出一个整数，表示经过所有操作后，最终剩下的那个数 $x$ 的最大可能值。

说明/提示

在第一个测试用例中，初始数组为 $a=[1,7,8,4,5]$。Pak Chanek 可以按如下方式操作：

1. 选择 $i=1$ 和 $j=2$，此时 $a=[8,4,5,4]$。
2. 选择 $i=3$ 和 $j=2$，此时 $a=[8,4,4]$。
3. 选择 $i=2$ 和 $j=3$，此时 $a=[8,4]$。
4. 选择 $i=1$ 和 $j=2$，此时 $a=[6]$。

所有操作结束后，数组只剩下一个元素 $x=6$。可以证明，没有任何一组操作序列能使最终的 $x$ 大于 $6$。

由 ChatGPT 4.1 翻译

样例

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

6
4
5