有 $$$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$$$ 的最大可能值。
示例
输入复制
722 -341 4 3 44-4 2 3 -65-2 -3 4 10 -95-12345678 -1000000000 -999999999 1000000000 -9999999992-7 157 -6 -1 -8 -8
输出复制
384152987654321-129
注意
在第一个测试用例中,圣诞老人将执行一次操作。如果他选择第一个孩子,他会将$$$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$$$ |