A. Значимое среднее
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Пака Чанека есть массив $$$a$$$ из $$$n$$$ целых положительных чисел. Поскольку в настоящее время он изучает, как вычислять среднее арифметическое двух чисел, он хочет попрактиковаться в этом на своем массиве $$$a$$$.

Пока в массиве $$$a$$$ есть хотя бы два элемента, Пак Чанек будет выполнять следующую трехшаговую операцию:

  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$$$. Найдите максимально возможное значение $$$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$$$ после применения всех операций.

Пример
Входные данные
3
5
1 7 8 4 5
3
2 6 5
5
5 5 5 5 5
Выходные данные
6
4
5
Примечание

В первом наборе входных данных массив изначально равен $$$a=[1,7,8,4,5]$$$. Пак Чанек выполнит следующие операции:

  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$$$.