У Пака Чанека есть массив \(a\) из \(n\) целых положительных чисел. Поскольку в настоящее время он изучает, как вычислять среднее арифметическое двух чисел, он хочет попрактиковаться в этом на своем массиве \(a\).
Пока в массиве \(a\) есть хотя бы два элемента, Пак Чанек будет выполнять следующую трехшаговую операцию:
- Выбрать два различных индекса \(i\) и \(j\) (\(1 \leq i, j \leq |a|\); \(i \neq j\)), где \(|a|\) обозначает текущий размер массива \(a\).
- Добавить \(\lfloor \frac{a_i+a_j}{2} \rfloor\)\(^{\text{∗}}\) в конец массива.
- Удалить из массива элементы \(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\), если Пак Чанек выполнит все операции оптимально.
Примечание
В первом наборе входных данных массив изначально равен \(a=[1,7,8,4,5]\). Пак Чанек выполнит следующие операции:
- Выбрать \(i=1\) и \(j=2\), тогда \(a=[8,4,5,4]\).
- Выбрать \(i=3\) и \(j=2\), тогда \(a=[8,4,4]\).
- Выбрать \(i=2\) и \(j=3\), тогда \(a=[8,4]\).
- Выбрать \(i=1\) и \(j=2\), тогда \(a=[6]\).
После всех операций массив состоит из одного элемента \(x=6\). Можно доказать, что не существует последовательности операций, в результате которой число \(x\) будет больше \(6\).