← 返回题目列表

Codeforces · 1844/C

C. 颗粒

中文机器翻译题面 查看原题

您在整数电荷为 $$$c_1,\dots,c_n$$$ 的线上发现了 $$$n$$$ 神秘粒子。您拥有一个允许您执行以下操作的设备:

- 选择一个粒子并将其从线上移除。剩余的粒子将移动以填充所产生的间隙。如果在被移除粒子的左侧和右侧直接存在带有电荷 $$$x$$$ 和 $$$y$$$ 的粒子,则它们会组合成单个电荷粒子 $$$x+y$$$。

例如,如果粒子线的电荷为 $$$[-3,1,4,-1,5,-9]$$$,则对第 $$$4$$$ 个粒子执行操作会将线转换为 $$$[-3,1,9,-9]$$$。

如果我们随后在这条新线中的 $$$1$$$st 粒子上使用该设备,该线将变成 $$$[1,9,-9]$$$。

您将执行操作,直到只剩下一个粒子。您可以获得的剩余粒子的最大电荷是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,输出一个整数,即剩余粒子的最大电荷。

示例

输入 #1

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

输出 #1

9
2994733059
-2718

注意

在第一个测试用例中,最佳策略是在第 $$$4$$$th 粒子上使用该设备,然后在 $$$1$$$st 粒子上使用该设备(如语句中所述),最后在新的 $$$3$$$rd 粒子上使用该设备,然后在 $$$1$$$st 粒子上使用该设备。

在第二个测试用例中,最佳策略是使用第 $$$4$$$th 粒子上的设备将线转换为 $$$[998244353,998244353,1996488706]$$$,然后在 $$$2$$$nd 粒子上将线转换为 $$$[2994733059]$$$。警惕整数溢出。

在第三个测试用例中,只有一个粒子,因此无法执行任何操作。