题目描述

给定一个包含 $n$ 个整数的数组 $a$。你需要将这 $n$ 个整数分成两个组 $s_1$ 和 $s_2$（组可以为空），使得满足以下条件：

• 对于每个 $i$ $(1 \leq i \leq n)$，$a_i$ 恰好属于一个组。
• $|sum(s_1)| - |sum(s_2)|$ 的值在所有分组方式中最大。这里 $sum(s_1)$ 表示组 $s_1$ 中所有数的和，$sum(s_2)$ 表示组 $s_2$ 中所有数的和。

请你求出 $|sum(s_1)| - |sum(s_2)|$ 的最大可能值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$ $(1 \leq t \leq 2 \cdot 10^4)$，表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(-10^9 \leq a_i \leq 10^9)$，表示数组 $a$ 的元素。

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

输出格式

对于每个测试用例，输出一个整数，表示 $|sum(s_1)| - |sum(s_2)|$ 的最大可能值。

说明/提示

在第一个测试用例中，可以分组为 $s_1 = \{10\}$，$s_2 = \{-10\}$。此时值为 $|10| - |-10| = 0$。

在第二个测试用例中，可以分组为 $s_1 = \{0, 11, -1\}$，$s_2 = \{-2\}$。此时值为 $|0 + 11 - 1| - |-2| = 10 - 2 = 8$。

在第三个测试用例中，可以分组为 $s_1 = \{2, 3, 2\}$，$s_2 = \{\}$。此时值为 $|2 + 3 + 2| - |0| = 7$。

在第四个测试用例中，可以分组为 $s_1 = \{-9, -4, 0\}$，$s_2 = \{2, 0\}$。此时值为 $|-9 - 4 + 0| - |2 + 0| = 13 - 2 = 11$。

由 ChatGPT 4.1 翻译

样例

4
2
10 -10
4
-2 -1 11 0
3
2 3 2
5
-9 2 0 0 -4

0
8
7
11