310508: CF1844C. Particles

C. Particlestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have discovered $n$ mysterious particles on a line with integer charges of $c_1,\dots,c_n$. You have a device that allows you to perform the following operation:

• Choose a particle and remove it from the line. The remaining particles will shift to fill in the gap that is created. If there were particles with charges $x$ and $y$ directly to the left and right of the removed particle, they combine into a single particle of charge $x+y$.

For example, if the line of particles had charges of $[-3,1,4,-1,5,-9]$, performing the operation on the $4$th particle will transform the line into $[-3,1,9,-9]$.

If we then use the device on the $1$st particle in this new line, the line will turn into $[1,9,-9]$.

You will perform operations until there is only one particle left. What is the maximum charge of this remaining particle that you can obtain?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $c_1,\dots,c_n$ ($-10^9 \le c_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output one integer, the maximum charge of the remaining particle.

ExampleInput

3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718

Output

9
2994733059
-2718

Note

In the first test case, the best strategy is to use the device on the $4$th particle, then on the $1$st particle (as described in the statement), and finally use the device on the new $3$rd particle followed by the $1$st particle.

In the second test case, the best strategy is to use the device on the $4$th particle to transform the line into $[998244353,998244353,1996488706]$, then on the $2$nd particle to transform the line into $[2994733059]$. Be wary of integer overflow.

In the third test case, there is only one particle, so no operations can be performed.

题目大意：
你发现了一条直线上的n个带有整数电荷的神秘粒子，它们的电荷分别是c1, ..., cn。你有一个设备，可以执行以下操作：
- 选择一个粒子并将其从直线中移除。剩余的粒子会移动以填充产生的空隙。如果被移除粒子的左右两侧直接相邻的粒子带有电荷x和y，它们会合并成一个带有电荷x+y的新粒子。

例如，如果粒子直线的电荷是[-3,1,4,-1,5,-9]，对第4个粒子执行操作将把直线变成[-3,1,9,-9]。

你要执行操作直到只剩下一个粒子。你能得到的剩余粒子的最大电荷是多少？

输入数据格式：
每个测试包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 10^4）。接下来是每个测试案例的描述。
每个测试案例的第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5）。
每个测试案例的第二行包含n个整数c1, ..., cn（-10^9 ≤ ci ≤ 10^9）。
保证所有测试案例的n之和不超过2 × 10^5。

输出数据格式：
对于每个测试案例，输出一个整数，即剩余粒子的最大电荷。

注意：
在第一个测试案例中，最好的策略是先对第4个粒子使用设备，然后对第1个粒子使用设备（如题目描述），最后对新直线上的第3个粒子使用设备，接着对第1个粒子使用设备。
在第二个测试案例中，最好的策略是先对第4个粒子使用设备，将直线变成[998244353,998244353,1996488706]，然后对第2个粒子使用设备，将直线变成[2994733059]。要注意整数溢出的问题。
在第三个测试案例中，只有一个粒子，所以不能执行任何操作。题目大意： 你发现了一条直线上的n个带有整数电荷的神秘粒子，它们的电荷分别是c1, ..., cn。你有一个设备，可以执行以下操作： - 选择一个粒子并将其从直线中移除。剩余的粒子会移动以填充产生的空隙。如果被移除粒子的左右两侧直接相邻的粒子带有电荷x和y，它们会合并成一个带有电荷x+y的新粒子。 例如，如果粒子直线的电荷是[-3,1,4,-1,5,-9]，对第4个粒子执行操作将把直线变成[-3,1,9,-9]。 你要执行操作直到只剩下一个粒子。你能得到的剩余粒子的最大电荷是多少？ 输入数据格式： 每个测试包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 10^4）。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5）。 每个测试案例的第二行包含n个整数c1, ..., cn（-10^9 ≤ ci ≤ 10^9）。 保证所有测试案例的n之和不超过2 × 10^5。 输出数据格式： 对于每个测试案例，输出一个整数，即剩余粒子的最大电荷。 注意： 在第一个测试案例中，最好的策略是先对第4个粒子使用设备，然后对第1个粒子使用设备（如题目描述），最后对新直线上的第3个粒子使用设备，接着对第1个粒子使用设备。 在第二个测试案例中，最好的策略是先对第4个粒子使用设备，将直线变成[998244353,998244353,1996488706]，然后对第2个粒子使用设备，将直线变成[2994733059]。要注意整数溢出的问题。 在第三个测试案例中，只有一个粒子，所以不能执行任何操作。