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

У вас есть массив $$$a$$$ длины $$$n$$$, состоящий из ненулевых целых чисел. Изначально у вас $$$0$$$ монет, и вы будете делать следующее, пока $$$a$$$ не станет пустым:

  • Пусть $$$m$$$ — текущая длина $$$a$$$. Выберите целое число $$$i$$$, где $$$1 \le i \le m$$$, и получите $$$|a_i|$$$$$$^{\text{∗}}$$$ монет, а затем:
    • если $$$a_i < 0$$$, то замените $$$a$$$ на $$$[a_1,a_2,\ldots,a_{i - 1}]$$$ (то есть удалите суффикс, начинающийся с $$$a_i$$$);
    • в противном случае замените $$$a$$$ на $$$[a_{i + 1},a_{i + 2},\ldots,a_m]$$$ (то есть удалите префикс, заканчивающийся на $$$a_i$$$).

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

$$$^{\text{∗}}$$$Здесь $$$|a_i|$$$ обозначает абсолютное значение $$$a_i$$$: оно равно $$$a_i$$$, когда $$$a_i > 0$$$, и $$$-a_i$$$, когда $$$a_i < 0$$$.

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

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

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

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

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

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

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

Пример
Входные данные
3
6
3 1 4 -1 -5 -9
6
-10 -3 -17 1 19 20
1
1
Выходные данные
23
40
1
Примечание

Пример того, как получить $$$23$$$ монеты в первом наборе входных данных, выглядит следующим образом:

  • $$$a = [3, 1, 4, -1, -5, \color{red}{-9}] \xrightarrow{i = 6} a = [3, 1, 4, -1, -5] $$$, и получите $$$9$$$ монет.
  • $$$a = [\color{red}{3}, 1, 4, -1, -5] \xrightarrow{i = 1} a = [1, 4, -1, -5] $$$, и получите $$$3$$$ монеты.
  • $$$a = [\color{red}{1}, 4, -1, -5] \xrightarrow{i = 1} a = [4, -1, -5] $$$, и получите $$$1$$$ монету.
  • $$$a = [4, -1, \color{red}{-5}] \xrightarrow{i = 3} a = [4, -1] $$$, и получите $$$5$$$ монет.
  • $$$a = [4, \color{red}{-1}] \xrightarrow{i = 2} a = [4] $$$, и получите $$$1$$$ монету.
  • $$$a = [\color{red}{4}] \xrightarrow{i = 1} a = [] $$$, и получите $$$4$$$ монеты.
После всех операций у вас будет $$$23$$$ монеты.

Пример того, как получить $$$40$$$ монет во втором наборе входных данных, выглядит следующим образом:

  • $$$a = [-10, -3, -17, \color{red}{1}, 19, 20] \xrightarrow{i = 4} a = [19, 20] $$$, и получите $$$1$$$ монету.
  • $$$a = [\color{red}{19}, 20] \xrightarrow{i = 1} a = [20] $$$, и получите $$$19$$$ монет.
  • $$$a = [\color{red}{20}] \xrightarrow{i = 1} a = [] $$$, и получите $$$20$$$ монет.
После всех операций у вас будет $$$40$$$ монет.