C. Частицы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы нашли $$$n$$$ волшебных частиц, которые расположены друг за другом в ряд и имеют целочисленные заряды $$$c_1,\dots,c_n$$$. У вас также есть устройство, которое позволяет производить следующую операцию:

  • Выбрать частицу и удалить её из последовательности. Оставшиеся частицы сдвинутся, чтобы заполнить образовавшийся разрыв между ними. Если перед удалением частицы непосредственно слева и непосредственно справа от неё были расположены частицы с зарядами $$$x$$$ и $$$y$$$ соответственно, то они войдут в реакцию и объединятся в одну частицу с зарядом $$$x+y$$$.

Например, если последовательность зарядов частиц была $$$[-3,1,4,-1,5,-9]$$$, то после выполнения операции над $$$4$$$-й частицей последовательность преобразуется в $$$[-3,1,9,-9]$$$.

Если после этого использовать устройство на $$$1$$$-й частице в этом новом порядке, то последовательность станет равна $$$[1,9,-9]$$$.

Вам нужно выполнять операции до тех пор, пока в последовательности не останется ровно одна частица. Чему равен максимально возможный заряд этой частицы?

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$c_1,\dots,c_n$$$ ($$$-10^9 \le c_i \le 10^9$$$).

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

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

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

Пример
Входные данные
3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718
Выходные данные
9
2994733059
-2718
Примечание

В первом наборе входных данных оптимальная стратегия выглядит так: использовать устройство на $$$4$$$-й частице, затем на $$$1$$$-й (как описано в условии), потом на $$$3$$$-й, и наконец на $$$1$$$-й.

Во втором наборе входных данных оптимальная стратегия выглядит так: использовать устройство на $$$4$$$-й частице, после чего последовательность преобразуется в $$$[998244353,998244353,1996488706]$$$, затем на $$$2$$$-й частице, после чего последовательность станет равна $$$[2994733059]$$$. Проследите за переполнением целочисленного типа.

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