题目描述

给定一个长度为 $n$ 的数组 $a$, 以及一个初值为 $0$ 的常数 $c$ 。然后，对于从 $1$ 到 $n$ 的每个 $i$ (按递增顺序)，执行以下的恰好一个操作:

• 操作1：把 $c$ 赋值为 $c+a_i$,
• 操作2：把 $c$ 赋值为 $|c+a_i|$ , 即 $c+a_i$ 的绝对值，

求出经过这一系列操作后 $c$ 可能达到的最大值。

输入格式

第一行输入一个整数 $t$。代表 $t$ 组询问。

接下来每组数据：

第一行输入一个整数 $n$。

接下来一行输入 $n$ 个整数 $a_1, a_2, ... , a_n$。

数据保证所有询问的 $\sum n$ 不超过 $3\times 10^5$。

输出格式

每组数据输出一行包含一个整数，表示最大值。

样例 1 输入

5
4
10 -9 -3 4
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4

样例 1 输出

6
24
6
4000000000
22

样例2输入及输出

file

数据规模与约定

对于 $30\%$ 的数据，满足 $t=1$, $2 \le n \le 100$, $-100\leq a_i\leq 100$ 。

对于 $100\%$ 的数据，满足 $1\leq t\leq 10^4$ , $2 \le n \le 2 \times 10^{5}$, $-10^9\leq a_i\leq 10^9$ , $\sum n\leq3\times 10^5$ 。

样例解释

在第一个测试用例中，如果我们在每次都执行操作2，结果是 $6$ 。可以证明这是最大结果。

在第三个测试用例中，最优的做法是先执行两次操作1，然后执行操作2，最后得到答案是 $6$。