CF1844C.Particles

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?

你在一条直线上发现了 $n$ 个神秘粒子，它们的电荷量分别为整数 $c_1,\dots,c_n$。你拥有一台设备，可执行如下操作：

• 选择一个粒子并将其从直线上移除。其余粒子将向中间移动以填补空缺。若被移除粒子的左侧和右侧紧邻粒子的电荷量分别为 $x$ 和 $y$，则这两个粒子将合并为一个电荷量为 $x+y$ 的新粒子。

例如，若粒子序列的电荷量为 $[-3,1,4,-1,5,-9]$，对第 $4$ 个粒子（即电荷为 $-1$ 的粒子）执行该操作后，序列将变为 $[-3,1,9,-9]$。

接着，若在新序列中对第 $1$ 个粒子（即电荷为 $-3$ 的粒子）执行该操作，则序列将变为 $[1,9,-9]$。

你将持续执行该操作，直到仅剩一个粒子。你能得到的该剩余粒子的最大电荷量是多少？

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $c_1,\dots,c_n$（$-10^9 \le c_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一个整数，表示剩余粒子的最大电荷量。

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.

在第一个测试用例中，最优策略是：首先对第 $4$ 个粒子使用该装置，然后对第 $1$ 个粒子使用（如题面所述），最后对新生成的第 $3$ 个粒子使用装置，再对第 $1$ 个粒子使用。

在第二个测试用例中，最优策略是：首先对第 $4$ 个粒子使用该装置，将序列变为 $[998244353,998244353,1996488706]$，再对第 $2$ 个粒子使用该装置，将序列变为 $[2994733059]$。请注意整数溢出问题。

在第三个测试用例中，仅存在一个粒子，因此无法执行任何操作。