Concate and count

时间限制：$1s$

空间限制：$256MB$

题目描述

有一个由 $n$ 个非零整数组成的序列 $a$ 。选择若干给定序列的子序列，并满足正负相间（即每个下一个元素的符号与当前元素的符号相反，如 $[+,-,+]$ ，或 $[-,+,-]$ 等等）且长度最大，记长度为 $k$ 。若有多个长度最长的满足要求的子序列，在所有长度 $k$ 的这些正负相间的子序列中，选择元素总和最大的一个并输出总和。

数据格式

输入

第一行输入一个整数 $t$ ，表示共有 $t$ 组测试用例；

对于每个测试用例，第一行输入一个正整数 $n$ ，表示数组 $a$ 的长度；

接下来一行输入 $n$ 个数字 $a_1,a_2......a_i\ (1 \leq i \leq n)$ 表示数组 $a$ 的元素。

输出

对于每个测试用例，输出一行一个整数，即最大正负相间的子序列的最大元素总和。

样例1

输入：

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. 在第一个样例中，选择的数据为 $[1,2,(3),(-1),-2]$ 。
2. 在第二个样例中，选择的数据为 $[-1,-2,(-1),-3]$ 。
3. 在第三个样例中，选择的数据为 $[(−2),8,3,(8),(−4),−15,(5),(−2),−3,(1)]$ 。
4. 在第四个样例中，所有数据均选择。

数据范围及约定

约定：对于所有测试用例，有 $\sum{n} \leq 2 * 10^5$ 。