题目描述：

小雨是一名热爱编程的高中生，同时也是热门冒险游戏《算法探险家》的忠实玩家。在这款游戏中，玩家需要在一个线性的游戏地图上进行探险，地图被划分为 n 个连续的区域，每个区域中都藏有一定数量的能量块，有些区域的能量块是正能量（可以为玩家补充能量），有些则是负能量（会消耗玩家能量）。

某天，游戏推出了一个新的挑战模式：玩家需要在地图上选择两个不重叠的连续区域进行探索，将这两个区域中的能量块全部收集起来。由于探索需要消耗时间和精力，玩家必须确保这两个区域不重叠，并且要让收集到的总能量最大。

请你帮助小雨计算出新挑战模式中能收集到的总能量的最大值是多少。

输入格式：

第一行是一个整数 T(≤30)，代表一共有多少组数据。 接下来是 T 组数据。 每组数据的第一行是一个整数n，代表能量块个数n(2≤n≤50000) ,第二行是 n 个整数 a1,a2,...,an(∣ai∣≤10000)。表示能量值。

输出格式：

T行，每行一个正整数，表示能收集到的最大能量值。

样例：

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

13

提示