题目内容

在一片古老的遗迹中，你发现了一排符石，从左到右编号为 $1$ 到 $n$。第 $i$ 块符石蕴含的能量值为 $v_i$（可能为正、负或零）。你可以从中挑选任意数量的符石（可以不选，也可以全部选择），并保持原有的相对顺序将这些符石拼接成一个新的序列。该序列将产生共鸣效应：序列中的第 $1$ 个符石贡献 $+v$，第 $2$ 个贡献 $-v$，第 $3$ 个贡献 $+v$，依此类推，符号正负交替。

若你选择了 $k$ 块符石，其能量依次为 $s_1, s_2, \ldots, s_k$，则共鸣总能量为

特别地，若不选任何符石，总能量视为 $0$。

你需要计算在该规则下所能获得的最大总能量。

约束条件

• 单组数据中符石个数 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。
• 每个能量值 $v_i$ 满足 $|v_i| \le 10^6$。

输入描述

第一行输入一个整数 $T$（$1 \le T \le 2 \times 10^5$），表示测试数据组数。 对于每组测试数据： 第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示该组符石的数量； 第二行输入 $n$ 个整数 $v_1, v_2, \ldots, v_n$（$|v_i| \le 10^6$），表示从左到右每块符石的能量值。 所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，代表可以得到的最大共鸣总能量。

样例1

输入

1
1
100

输出

100

说明

仅有一块符石，能量为 100。可选的方案有两种：

1. 不选任何符石，共鸣总能量为 0；
2. 选择该符石，序列为 [100]，共鸣能量为 $+100$。 显然最大总能量为 100。此样例测试了 $n=1$ 的边界情况。

样例2

输入

1
4
-3 -1 -4 -2

输出

3

说明

四块符石能量全为负，分别为 -3、-1、-4、-2。

最优方案是选择第 2 块和第 3 块符石，子序列为 [-1, -4]。 共鸣总能量计算：$E = s_1 - s_2 = (-1) - (-4) = 3$。

其他可能的选择：只选一块最多为 -1；选两块若取 -3 和 -4 得 $(-3)-(-4)=1$；选三块或四块均小于 3。因此最大总能量为 3。此样例说明全负数组可通过合理选择获得正值。

样例3

输入

1
5
5 -3 4 -2 6

输出

20

说明

五块符石能量依次为 5、-3、4、-2、6。

最优方案是选择全部五块符石，子序列为原序列本身。 其共鸣总能量为：

若尝试丢弃某些符石，例如丢弃 -3 和 -2，子序列为 [5, 4, 6]，能量为 $5 - 4 + 6 = 7$，比 20 小。全选时所有负数恰好位于减数位置，使它们变为正贡献，因此总能量达到最大 20。