← 返回题目列表

Codeforces · 2178/C

C. 第一或第二

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

有 $$$n$$$ 个孩子排成一排,其中 善良 第 $$$i$$$ 个孩子的 是 $$$a_i$$$。圣诞老人正在决定哪些孩子属于好孩子名单,哪些孩子属于顽皮孩子名单。

整数 $$$X$$$ 最初设置为 $$$0$$$。圣诞老人将执行以下操作 正是 $$$n-1$$$ 次:

  • 选择队列中的第一个或第二个孩子并将其从队列中删除。
  • 设 $$$w$$$ 为 所选孩子的 善良 第 $$$i$$$ 个孩子的 。
    • 如果选择了第一个孩子,请将其添加到好列表中,并将 $$$w$$$ 添加到 $$$X$$$。
    • 如果选择了第二个孩子,请将他们添加到淘气列表中,并从 $$$X$$$ 中减去 $$$w$$$。

请注意,在所有操作之后,只有一个子项仍未分配给列表。

确定圣诞老人在所有 $$$n-1$$$ 操作后可以获得的 $$$X$$$ 的最大可能值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 子级的数量。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$) — 每个孩子的 善良 第 $$$i$$$ 个孩子的 。

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

输出

对于每个测试用例,打印一个整数 - 圣诞老人在所有 $$$n-1$$$ 操作后可以获得的 $$$X$$$ 的最大可能值。

示例

输入
复制

7
2
2 -3
4
1 4 3 4
4
-4 2 3 -6
5
-2 -3 4 10 -9
5
-12345678 -1000000000 -999999999 1000000000 -999999999
2
-7 1
5
7 -6 -1 -8 -8

输出
复制

3
8
4
15
2987654321
-1
29

注意

在第一个测试用例中,圣诞老人将执行一次操作。如果他选择第一个孩子,他会将$$$a_1=2$$$与$$$X$$$相加,得到$$$X=2$$$;如果他选择第二个孩子,他将从$$$X$$$中减去$$$a_2=-3$$$,得到$$$X=3$$$。因此,答案是$$$3$$$。

在第二个测试用例中,最佳选择是在所有三个操作中选择第一个子项。 $$$X$$$ 的值为 $$$1+4+3=8$$$。

在第三个测试用例中,以下是最佳操作顺序:

#类型很好 剩余儿童的 剩下的孩子操作后$$$X$$$
0—$$$[-4, 2, 3, -6]$$$$$$0$$$
1第一$$$[2, 3, -6]$$$$$$-4$$$
2第一$$$[3, -6]$$$$$$-2$$$
3第二$$$[3]$$$$$$4$$$

在第四个测试用例中,以下是最佳操作顺序:

#类型很好 剩余儿童的 剩下的孩子操作后$$$X$$$
0—$$$[-2, -3, 4, 10, -9]$$$$$$0$$$
1第二$$$[-2, 4, 10, -9]$$$$$$3$$$
2第一$$$[4, 10, -9]$$$$$$1$$$
3第一$$$[10, -9]$$$$$$5$$$
4第一$$$[-9]$$$$$$15$$$