Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×
B. Третья сторона
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Розовые солдаты дали вам последовательность $$$a$$$, состоящую из $$$n$$$ положительных целых чисел.

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

  • Выберите два различных индекса $$$i$$$ и $$$j$$$.
  • Затем выберите положительное целое число $$$x$$$, такое что существует невырожденный треугольник$$$^{\text{∗}}$$$ со сторонами $$$a_i$$$, $$$a_j$$$ и $$$x$$$.
  • Наконец, удалите два элемента $$$a_i$$$ и $$$a_j$$$, и добавьте $$$x$$$ в конец $$$a$$$.

Найдите максимальное возможное значение единственного последнего элемента в последовательности $$$a$$$.

$$$^{\text{∗}}$$$Треугольник со сторонами длиной $$$a$$$, $$$b$$$, $$$c$$$ является невырожденным, если $$$a+b > c$$$, $$$a+c > b$$$, $$$b+c > a$$$.

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

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

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

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

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

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

Для каждого набора входных данных выведите максимальное возможное значение единственного последнего элемента на отдельной строке.

Пример
Входные данные
4
1
10
3
998 244 353
5
1 2 3 4 5
9
9 9 8 2 4 4 3 5 3
Выходные данные
10
1593
11
39
Примечание

В первом примере уже есть только один элемент. Значение единственного последнего элемента равно $$$10$$$.

Во втором примере $$$a$$$ изначально равен $$$[998,244,353]$$$. Одна из оптимальных последовательностей операций:

  1. Удалите $$$a_2=244$$$ и $$$a_3=353$$$, и добавьте $$$596$$$ в конец $$$a$$$. Теперь $$$a$$$ равен $$$[998,596]$$$.
  2. Удалите $$$a_1=998$$$ и $$$a_2=596$$$, и добавьте $$$1593$$$ в конец $$$a$$$. Теперь $$$a$$$ равен $$$[1593]$$$.

Можно показать, что единственный последний элемент не может быть больше $$$1593$$$. Поэтому ответ равен $$$1593$$$.