1454: 物理魔法师II
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：40
Solved：16
Description
众所周知,小明是魔法世界的大物理学家。
在魔法师的斗争中脱身后，小明急需补充他的弹药。
弹药的原材料是一种神秘导体。导体分为 $n$ 段,每段所带的相对电荷为$a_i$。
小明可以进行任意次如下操作：
假定当前导体段数为 $m$ ,编号依次为$1,2,...m$ 。小明可以选择第 $i (1 < i <m)$段导体将激发电性，该段导体消失，第 $i-1$与$i+1$段导体将会融合成一段相对电荷为$a_{i-1}+a_{i+1}$的导体。接着我们重新依次对导体段编号，融合后段数变为$m-2$，但导体段的相对顺序不变。
任意时刻，小明可以取导体中的任意一段制作电球。
他能得到的导体的最大相对电荷是多少？
在魔法师的斗争中脱身后，小明急需补充他的弹药。
弹药的原材料是一种神秘导体。导体分为 $n$ 段,每段所带的相对电荷为$a_i$。
小明可以进行任意次如下操作：
假定当前导体段数为 $m$ ,编号依次为$1,2,...m$ 。小明可以选择第 $i (1 < i <m)$段导体将激发电性，该段导体消失，第 $i-1$与$i+1$段导体将会融合成一段相对电荷为$a_{i-1}+a_{i+1}$的导体。接着我们重新依次对导体段编号，融合后段数变为$m-2$，但导体段的相对顺序不变。
任意时刻，小明可以取导体中的任意一段制作电球。
他能得到的导体的最大相对电荷是多少？
Input
第一行，一个整数 $t$ ,代表测试点数。
每组测试点第一行，一个整数 $n$ ， 代表导体的段数。
每组测试点第二行，$n$ 个整数，第 $i$ 个整数 $a_{i}$ 代表第 $i$ 段导体的相对电荷。
数据范围:
$1 \le t \le 10^4$
$1 \le n \le 2*10^5$
$-10^9 \le a_{i} \le 10^9$
保证所有测试点的 $n$ 之和不大于 $2*10^5$
Output
$t$行,每行一个整数，第 $i$ 个整数代表第 $i$ 组测试点的答案。
Sample Input Copy
5
2
12 -3
6
1 1 -4 5 -1 4
1
-100
5
5 4 -3 2 1
6
999999999 999999999 999999999 999999999 999999998 999999999
Sample Output Copy
12
10
-100
6
2999999997