题目描述

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

$$d(A) = \max_{1 \le s_1 \le t_1 < s_2 \le t_2 \le n} \left\{ \sum_{i=s_1}^{t_1} a_i + \sum_{j=s_2}^{t_2} a_j \right\} $$

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

输入

第一行是一个整数 $T$（$\le 30$），代表一共有多少组数据。

接下来是 $T$ 组数据。

每组数据的第一行是一个整数 $n$（$2 \le n \le 50000$），第二行是 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$|a_i| \le 10000$）。

输出

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

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

13