#OJ2248. 书

书

书

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

  wx有一本古老的魔法书,魔法书中有很多古老的咒语。每句咒语都蕴含着巨大的能量,现在wx必须利用咒语去打败恶龙,救出公主hjh。要想打败恶龙就必须要先知道咒语中的魔力是多少,据说一句咒语中的每段子咒语都会对咒语的魔力有贡献,但是断开的子咒语是没有作用的。现在给你一句咒语中每个咒文的魔力ai,请你帮wx计算一下这句咒语的最大魔力是多少。

Input

第一行输入一个T,表示有T组输入。接下来有T个输入。

每一组输入分为两行,第一行包含一个数字N (1 <= N <= 100000),表示咒语的长度。第二行输入咒语中的N个咒文的魔力值ai(0< ai <=1000000)

Output

对于每一个输入,在一行中输出这句咒语的最大魔力值。

Sample Input

3
5
1 2 3 4 5
3
2 3 3
4
2 3 3 2

Sample Output

105
27
52

HINT

第二组样例: 求所有连续子序列的和 :2 + 3 + 3 + (2 + 3) + (3 + 3) + (2 + 3 + 3) = 27 可以分别计算每个数字对于结果的贡献是多少(也就是每个数字能出现多少次,Hint君只能帮你到这里了~)

Append Code