#u1007. 小卉的特殊序列

小卉的特殊序列

题目描述

小卉刚刚学习了子序列的定义。如果bb可以通过aa删除零个或者多个元素而不改变剩余元素的顺序得到,则序列bbaa的子序列。例如:如果a=[1,2,3,4,5,1,2]a=[1,2,3,4,5,1,2],则可能的子序列为:[1,2,3],[1][1,2,3],[1][1,2,3,4,5,1,2][1,2,3,4,5,1,2], 但是[1,1,3][1,1,3]不是aa的子序列。

现在小卉想知道给定一个由正数和负数组成的序列aa(序列中没有零),那么序列aa最长的交叉子序列中元素和最大的是多少。交叉子序列,指的是子序列中每下一个元素的符号与当前元素的符号相反,如正、负、正或者负、正、负等。

换句话说,小卉想请你找到最长的交叉子序列中元素和最大的那个,然后输出最大的元素和。

输入

第一行包含一个整数t(1t104)t(1\leq t\leq 10^4),样例的数量。 接下来的tt个样例中 第一行包含一个整数n(1n2×105)n(1\leq n\leq 2\times 10^5),表示序列a中元素的数量。 第二行包含nn个整数a1,a2,a3ana_1,a_2,a_3……a_n(109ai109,ai(-10^9\leq a_i\leq 10^9,a_i不等于0) 保证每个样例中nn的总和不超过2×1052\times 10^5.

输出

对于每一个样例,输出答案:最长交叉子序列的元素和。

Samples

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