CF1933A.Turtle Puzzle: Rearrange and Negate

You are given an array $a$ of $n$ integers. You must perform the following two operations on the array (the first, then the second):

1. Arbitrarily rearrange the elements of the array or leave the order of its elements unchanged.
2. Choose at most one contiguous segment of elements and replace the signs of all elements in this segment with their opposites. Formally, you can choose a pair of indices $l, r$ such that $1 \le l \le r \le n$ and assign $a_i = -a_i$ for all $l \le i \le r$ (negate elements). Note that you may choose not to select a pair of indices and leave all the signs of the elements unchanged.

What is the maximum sum of the array elements after performing these two operations (the first, then the second)?

给你一个包含 $n$ 个整数的数组 $a$。你必须对该数组执行以下两个操作（先执行第一个，再执行第二个）：

1. 任意重排数组中的元素，或者保持其元素顺序不变。
2. 选择至多一个连续子段，并将该子段中所有元素的符号取反（即变为相反数）。形式化地说，你可以选择一对下标 $l, r$，满足 $1 \le l \le r \le n$，并对所有满足 $l \le i \le r$ 的 $i$，令 $a_i = -a_i$（对元素取负）。注意，你也可以不选择任何下标对，从而保持所有元素的符号不变。

在执行完这两个操作（先执行第一个，再执行第二个）后，数组元素之和的最大值是多少？

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 50$) — the number of elements in array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-100 \le a_i \le 100$) — elements of the array.

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$）—— 表示数组 $a$ 中元素的个数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-100 \le a_i \le 100$）—— 表示数组的元素。

For each test case, output the maximum sum of the array elements after sequentially performing the two given operations.

对于每个测试用例，输出依次执行给定的两个操作后，数组元素的最大和。

In the first test case, you can first rearrange the array to get $[3,-2,-3]$ (operation 1), then choose $l = 2, r = 3$ and get the sum $3 + -((-2) + (-3)) = 8$ (operation 2).

In the second test case, you can do nothing in both operations and get the sum $0$.

In the third test case, you can do nothing in both operations and get the sum $0 + 1 = 1$.

In the fourth test case, you can first leave the order unchanged (operation 1), then choose $l = 1, r = 1$ and get the sum $-(-99) = 99$ (operation 2).

In the fifth test case, you can first leave the order unchanged (operation 1), then choose $l = 2, r = 3$ and get the sum $10 + -((-2) + (-3)) + 7 = 22$ (operation 2).

In the sixth test case, you can first leave the order unchanged (operation 1), then choose $l = 1, r = 5$ and get the sum $-((-1)+(-2)+(-3)+(-4)+(-5))=15$ (operation 2).

在第一个测试用例中，你可以首先重新排列数组得到 $[3,-2,-3]$（操作 1），然后选择 $l = 2, r = 3$，得到和为 $3 + -((-2) + (-3)) = 8$（操作 2）。

在第二个测试用例中，你可以在两个操作中均不进行任何操作，得到和为 $0$。

在第三个测试用例中，你可以在两个操作中均不进行任何操作，得到和为 $0 + 1 = 1$。

在第四个测试用例中，你可以首先保持顺序不变（操作 1），然后选择 $l = 1, r = 1$，得到和为 $-(-99) = 99$（操作 2）。

在第五个测试用例中，你可以首先保持顺序不变（操作 1），然后选择 $l = 2, r = 3$，得到和为 $10 + -((-2) + (-3)) + 7 = 22$（操作 2）。

在第六个测试用例中，你可以首先保持顺序不变（操作 1），然后选择 $l = 1, r = 5$，得到和为 $-((-1)+(-2)+(-3)+(-4)+(-5))=15$（操作 2）。