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

Напомним, что последовательность $$$b$$$ является подпоследовательностью последовательности $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ путем удаления нуля или более элементов без изменения порядка оставшихся элементов. Например, если $$$a=[1, 2, 1, 3, 1, 2, 1]$$$, то возможные подпоследовательности: $$$[1, 1, 1, 1]$$$, $$$[3]$$$ и $$$[1, 2, 1, 3, 1, 2, 1]$$$, но не $$$[3, 2, 3]$$$ и $$$[1, 1, 1, 1, 2]$$$.

Вам задана последовательность $$$a$$$, состоящая из $$$n$$$ положительных и отрицательных элементов (в последовательности нет нулей).

Ваша задача выбрать максимальную по размеру (длине) чередующуюся подпоследовательность заданной последовательности (то есть знак каждого следующего элемента противоположен знаку текущего элемента, например, положительный-отрицательный-положительный и так далее или отрицательный-положительный-отрицательный и так далее). Из всех таких подпоследовательностей вам нужно выбрать ту, которая имеет максимальную сумму элементов.

Другими словами, если максимальная длина чередующейся подпоследовательности равна $$$k$$$, то ваша задача — найти максимальную сумму элементов какой-то чередующейся подпоследовательности длины $$$k$$$.

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

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

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

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в $$$a$$$. Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9, a_i \ne 0$$$), где $$$a_i$$$ — $$$i$$$-й элемент в $$$a$$$.

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

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

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

Пример
Входные данные
4
5
1 2 3 -1 -2
4
-1 -2 -1 -3
10
-2 8 3 8 -4 -15 5 -2 -3 1
6
1 -1000000000 1 -1000000000 1 -1000000000
Выходные данные
2
-1
6
-2999999997
Примечание

В первом наборе тестовых данных примера одним из возможных ответов является $$$[1, 2, \underline{3}, \underline{-1}, -2]$$$.

Во втором наборе тестовых данных примера одним из возможных ответов является $$$[-1, -2, \underline{-1}, -3]$$$.

В третьем наборе тестовых данных примера одним из возможных ответов является $$$[\underline{-2}, 8, 3, \underline{8}, \underline{-4}, -15, \underline{5}, \underline{-2}, -3, \underline{1}]$$$.

В четвертом наборе тестовых данных примера одним из возможных ответов является $$$[\underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}]$$$.