题目描述

对于给定的整数序列 $A=\{a_1, a_2, \ldots, a_n\}$，找出两个不重合连续子段，使得两子段中所有数字的和最大。我们如下定义函数：

$$d(A) = \max\{a_i + a_{i+1} + \ldots + a_j + a_k + a_{k+1} + \ldots + a_l\}$$

其中 $1 \le i \le j < k \le l \le n$。

我们的目标就是求出 $d(A)$。

输入格式

第一行是一个整数 $T$，代表一共有多少组数据。

接下来是 $T$ 组数据。每组数据的第一行是一个整数，代表数据个数 $n$，第二行是 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出一个整数，就是 $d(A)$ 的值。

样例

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

13

数据范围

• $T \le 30$
• $2 \le n \le 50000$
• $|a_i| \le 10000$

提示

样例取 $\{2,2,3,-3,4\}$ 和 $\{5\}$，最大和为 $13$。