D28:maximum sum (maximum sum, translation)

The original title is ：OpenJudge - 1481:Maximum sum

translate ：

describe ： Give a group n It's an integer :A={a1,a2,...,an}, We define functions d(A) as follows :

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

Your task is to calculate d(A). Output only one line for each test case . This line should contain integers d(A);

Input ： Input by T（T<=30) A test case consists of , The number of test cases (T) In the first line of input . Each test case contains two lines . The first line is an integer n(2<=n<=50000). The second line contains n It's an integer :a1,a2,..., One .(|ai| <= 10000). There is a blank line after each case ;

Output ： Print one line for each test case , Contains integers d(A);

Tips ： In the sample input , We choose {2,2,3,-3,4} and {5}, You can get the answer . The input is huge , Suggest using scanf.