题目描述

给定一个整数序列，选择两个不重叠的连续子段，使这两个子段内所有数的总和最大。

两个子段都必须非空，可以相邻，也可以隔着一些没有选择的元素。即选择下标满足1≤s₁≤t₁<s₂≤t₂≤n，最大化两个区间的元素和。

输入格式

第一行整数T，表示数据组数。每组数据第一行整数n，第二行n个整数，表示序列。

输出格式

每组数据输出一行，表示两个子段的最大总和。

样例

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

13

数据范围

1≤T≤30，2≤n≤50000；每个元素是绝对值不超过10000的整数。