题目描述

强哥在一家科技公司工作，最近他负责优化一个重要的数据分析项目。项目中有这样一个问题：

给定一个整数序列 $A = \{a_1, a_2, ..., a_n\}$，强哥需要从这个序列中找出两个互不重叠的连续子段，使得这两个子段中所有数字的和达到最大。

这个问题的目标是计算出这个最大值，我们用函数 $d(A)$ 来表示这个最大值。

这个问题就像是工作中寻找两个最佳的协作时间段：每个子段代表一个团队在某段时间内的产出值（正数表示收益，负数表示成本），强哥需要选择两个不相交的时间段，让团队的总产出最大化，从而为公司创造最大价值。这既锻炼了他分析问题的能力，也体现了在工作中寻找最优解决方案的积极态度。

输入格式

第一行是一个整数 $T$ ($T \leq 30$)，代表一共有多少组测试数据。

接下来是 $T$ 组数据。

每组数据的第一行是一个整数 $n$ ($2 \leq n \leq 50000$)，代表序列的长度。

第二行是 $n$ 个整数 $a_1, a_2, ..., a_n$ ($|a_i| \leq 10000$)。

注意： 输入数据可能较大，请选择高效的算法。

输出格式

对于每组数据，输出一个整数，就是 $d(A)$ 的值。

输入样例

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

输出样例

13