Concate and count

时间限制：1s

空间限制：256MB

题目描述

有一个由 \(n\) 个非零整数组成的序列 \(a\) 。选择若干给定序列的子序列构成\(L\)，要求\(L\)满足正负相间。输出长度最大的\(L\)的元素总和。如果长度最大的\(L\)不止一个，那么输出元素总和最大的那个。
正负相间是指 每个元素的符号都与它前一个元素的符号相反，如 \([+,-,+]\) ，或 \([-,+,-]\) 等等
元素总和是指 这个序列中，所有整数的和，如\([1,-1,2,-3]\)的元素总和是\(1+(-1)+2+(-3)=-1\).

数据格式

输入

第一行输入一个整数 \(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. 在第四个样例中，所有数据均选择。

数据范围及约定

测试点编号	约定	测试点分值
1~2	\(t=1,1 \leq n \leq 100,−100 \leq a_i \leq 100\)	每个测试点 10 分
3~4	\(t=1,1 \leq n \leq 2*10^5,−10^9 \leq a_i \leq 10^9\)	每个测试点 10 分
6~10	\(t \leq 10^4,1 \leq n \leq 2*10^5,−10^9 \leq a_i \leq 10^9\)	每个测试点 10 分

约定：对于所有测试用例，有 \(\sum{n} \leq 2 * 10^5\) 且 \(a_i≠0\) 。