B. Оптимальное разбиение
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Ваша задача — разбить $$$a$$$ на непустые подотрезки (всего существует $$$2^{n-1}$$$ таких разбиений).

Пусть $$$s=a_l+a_{l+1}+\ldots+a_r$$$. Значение подмассива $$$a_l, a_{l+1}, \ldots, a_r$$$ равно:

  • $$$(r-l+1)$$$, если $$$s>0$$$,
  • $$$0$$$, если $$$s=0$$$,
  • $$$-(r-l+1)$$$, если $$$s<0$$$.
Какую максимальную сумму значений подотрезков можно получить при оптимальном разбиении?
Входные данные

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

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

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

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

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

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

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

Пример $$$1$$$: одно из оптимальных разбиений выглядит так: $$$[1, 2]$$$, $$$[-3]$$$. $$$1+2>0$$$, поэтому величина $$$[1, 2]$$$ равна $$$2$$$. $$$-3<0$$$, поэтому величина $$$[-3]$$$ равна $$$-1$$$. $$$2+(-1)=1$$$.

Пример $$$2$$$: возможное оптимальное разбиение выглядит так: $$$[0, -2, 3]$$$, $$$[-4]$$$, сумма величин подотрезков равна $$$3+(-1)=2$$$.