У Пака Чанека есть массив $$$a$$$ из $$$n$$$ целых положительных чисел. Поскольку в настоящее время он изучает, как вычислять среднее арифметическое двух чисел, он хочет попрактиковаться в этом на своем массиве $$$a$$$.
Пока в массиве $$$a$$$ есть хотя бы два элемента, Пак Чанек будет выполнять следующую трехшаговую операцию:
Например, предположим, что $$$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$$$ после применения всех операций.
351 7 8 4 532 6 555 5 5 5 5
6 4 5
В первом наборе входных данных массив изначально равен $$$a=[1,7,8,4,5]$$$. Пак Чанек выполнит следующие операции:
После всех операций массив состоит из одного элемента $$$x=6$$$. Можно доказать, что не существует последовательности операций, в результате которой число $$$x$$$ будет больше $$$6$$$.
Название |
---|