Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×
Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Ералим, будучи боссом мафии, управляет группой из $$$n$$$ бойцов. Боец $$$i$$$ обладает рейтингом $$$a_i$$$.

Ералим устраивает турнир из $$$n - 1$$$ боёв, в каждом из которых выбираются два ещё не выбывших бойца $$$i$$$ и $$$j$$$ ($$$1 \le i < j \le n$$$). В результате боя боец $$$i$$$ выбывает из турнира, а рейтинг бойца $$$j$$$ уменьшается на величину рейтинга бойца $$$i$$$. То есть $$$a_j$$$ уменьшается на $$$a_i$$$. Обратите внимание, что рейтинг бойца $$$j$$$ может стать отрицательным. При этом номера бойцов не меняются.

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

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — рейтинги бойцов.

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

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

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

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

В первом примере можно организовать бой между бойцами с индексами $$$1$$$ и $$$2$$$, где боец с индексом $$$2$$$ выиграет. Тогда рейтинг последнего бойца, то есть бойца с индексом $$$2$$$, будет $$$1 - 2 = -1$$$.

Во втором примере можно сначала провести бой между бойцами с индексами $$$1$$$ и $$$2$$$, где победит боец с индексом $$$2$$$, а затем провести бой между бойцами с индексами $$$2$$$ и $$$3$$$, где победит боец с индексом $$$3$$$.

Рейтинг бойца с индексом $$$2$$$ после первого боя будет $$$2 - 2 = 0$$$. Рейтинг бойца с индексом $$$3$$$ после второго боя будет $$$8 - 0 = 8$$$.