题目描述

给定一个整数序列，请你找出两个不重合的连续子段，使得这两个子段内所有数字的和最大。请计算这个最大和。

输入格式

第一行：一个整数 $T$，表示数据组数。

接下来 $T$ 组数据：

• 每组数据第一行：一个整数 $n$，表示序列长度。
• 每组数据第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的元素。

输出格式

对于每组数据，输出一行一个整数，即满足条件的最大和。

样例

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

13

样例解释 对于样例序列 1 -1 2 2 3 -3 4 -4 5 -5，一种最优的选择是：

• 第一个连续子段：1 -1 2 2 3 -3 4，和为 $8$；
• 第二个连续子段：5，和为 $5$。 两个子段不重合，总和为 $8+5=13$，即为最大和。

数据范围

• $1 \le T \le 30$
• $2 \le n \le 100000$
• $|a_i| \le 1000000$