CFCF2178C.First or Second

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $n$ 个孩子站成一排，第 $i$ 个孩子的友善值为 $a_i$ 。圣诞老人正在决定哪些孩子应列入友善名单，哪些孩子应列入调皮名单。

有一个整数 $X$ ，初始值为 $0$ 。圣诞老人将恰好进行 $n-1$ 次如下操作：

从队伍的第一个或第二个孩子中选择一个，将他移出队伍。
记被选中孩子的友善值为 $w$ $w$ 。
- 如果选择了第一个孩子，则把他加入友善名单，并将 $w$ 加到 $X$ 上。
- 如果选择了第二个孩子，则把他加入调皮名单，并将 $w$ 从 $X$ 中减去。

注意，所有操作后，有且仅有一个孩子没有被分配到任何名单。

请你计算，所有 $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$ ）——每个孩子的友善值。

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

输出格式

对于每个测试用例，输出一个整数，表示圣诞老人能获得的 $X$ 的最大可能值。

输入输出样例

输入#1

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

输出#1

说明/提示

在第一个测试用例中，圣诞老人只需进行一次操作。如果他选择第一个孩子，将 $a_1=2$ 加入 $X$ ，得到 $X=2$ ；如果他选择第二个孩子，将 $a_2=-3$ 从 $X$ 中减去，得到 $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$ 。

首页