CF1747A.Two Groups

You are given an array $a$ consisting of $n$ integers. You want to distribute these $n$ integers into two groups $s_1$ and $s_2$ (groups can be empty) so that the following conditions are satisfied:

• For each $i$ $(1 \leq i \leq n)$, $a_i$ goes into exactly one group.

• The value $|sum(s_1)| - |sum(s_2)|$ is the maximum possible among all such ways to distribute the integers.

  Here $sum(s_1)$ denotes the sum of the numbers in the group $s_1$, and $sum(s_2)$ denotes the sum of the numbers in the group $s_2$.

Determine the maximum possible value of $|sum(s_1)| - |sum(s_2)|$.

给你一个包含 $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)|$ 的最大可能值。

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 2 \cdot 10^4)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(1 \leq n \leq 10^5)$ — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2 \ldots a_n$ $(-10^9 \leq a_i \leq 10^9)$ — elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the maximum possible value of $|sum(s_1)| - |sum(s_2)|$.

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

In the first testcase, we can distribute as $s_1 = {10}$, $s_2 = {-10}$. Then the value will be $|10| - |-10| = 0$.

In the second testcase, we can distribute as $s_1 = {0, 11, -1}$, $s_2 = {-2}$. Then the value will be $|0 + 11 - 1| - |-2| = 10 - 2 = 8$.

In the third testcase, we can distribute as $s_1 = {2, 3, 2}$, $s_2 = {}$. Then the value will be $|2 + 3 + 2| - |0| = 7$.

In the fourth testcase, we can distribute as $s_1 = {-9, -4, 0}$, $s_2 = {2, 0}$. Then the value will be $|-9 - 4 + 0| - |2 + 0| = 13 - 2 = 11$.

在第一个测试用例中，我们可以分配为 $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$。