Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

C. Математика и физика
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд расположены $$$n$$$ атомных ядер, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Изначальная масса $$$i$$$-го ядра равна $$$a_i$$$.

За одну операцию можно выбрать ядро $$$i$$$ ($$$1 \le i \le k$$$, где $$$k$$$ — текущее количество ядер), масса которого $$$a_i \ge 2$$$. Затем это ядро разделяется на две части с положительными целыми массами $$$x$$$ и $$$y$$$ такими, что $$$x \ge 1$$$, $$$y \ge 1$$$ и $$$x + y = a_i$$$.

После разделения $$$i$$$-е ядро удаляется из последовательности, уменьшая общее количество ядер на $$$1$$$. Масса $$$x$$$ добавляется к левому соседу удалённого ядра, если он существует. Масса $$$y$$$ добавляется к правому соседу удалённого ядра, если он существует. Если соответствующего соседа нет, эта масса теряется в окружающей среде.

Последовательность сразу сдвигается, заполняя образовавшийся промежуток. Процесс заканчивается, когда больше нельзя выполнить ни одной операции.

Определите, можно ли завершить процесс так, чтобы осталось ровно одно ядро. Если это возможно, найдите максимально возможную массу этого единственного оставшегося ядра.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — изначальное количество атомных ядер.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — изначальные массы ядер.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможную массу единственного оставшегося ядра. Если невозможно завершить процесс так, чтобы осталось ровно одно ядро, выведите $$$-1$$$.

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

Рассмотрим первый набор входных данных. Изначальная последовательность равна $$$[1, 2, 3, 4]$$$. Оптимальная последовательность операций следующая:

  • Разделим ядро массой $$$2$$$ на части $$$x = 1$$$, $$$y = 1$$$: последовательность станет равна $$$[1 + 1, 3 + 1, 4] = [2, 4, 4]$$$.
  • Разделим первое ядро массой $$$4$$$ на части $$$x = 1$$$, $$$y = 3$$$: последовательность станет равна $$$[2 + 1, 4 + 3] = [3, 7]$$$.
  • Разделим ядро массой $$$3$$$ на части $$$x=1, y=2$$$. Масса $$$1$$$ безвозвратно теряется слева, а масса $$$2$$$ добавляется к правому ядру. Итоговая последовательность равна $$$[7 + 2] = [9]$$$.

Теперь осталось ровно одно ядро массой $$$9$$$. Можно показать, что это максимально возможная масса.

Во втором наборе входных данных невозможно выполнить ни одной операции, поэтому невозможно получить последовательность, состоящую из одного ядра. Следовательно, нужно вывести $$$-1$$$.