题目描述

小T给了小L一个序列，但是小L她现在想从里面选出两个序列。原序列为a1, a2... an，选出

                     t1     t2 
         d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n }
                     i=s1   j=s2

也就是选出两个不相交的连续序列，使得他们的和最大。

输入格式

本题有多组数据，第一行一个整数T，表示数据组数

下面T组数据，对于每一组数据:

第一行一个正整数n，表示小L的序列的长度。第二行n个整数，表示小L的序列

输出格式

对于每一组数据，输出正确答案

样例

#input

1
10
1 -1 2 2 3 -3 4 -4 5 -5

#output

13

#解释

其中一种最优的选法是：选择 2 2 3 -3 4和 5 这两个连续子序列。和为13

数据范围与提示

T <= 10

n <= 500000

序列中的每个数∈[-50, 50]