A. 乌龟谜题：重排与取反
每测试点时间限制：2 秒
内存限制：256 兆字节

题目描述

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

1. 任意重排数组中的元素，也可以保持原顺序不变。
2. 选择至多一个连续子段，将该子段中所有元素的符号取反。
   形式上，你可以选择一对下标 $l, r$ 满足 $1 \le l \le r \le n$，然后对于所有 $l \le i \le r$，令 $a_i = -a_i$（即取反）。
   注意：你也可以不选择任何子段，即保持所有元素的符号不变。

问：在依次执行这两个操作后，数组元素的和最大可能是多少？

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。
接下来每个测试用例的描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 50$），表示数组 $a$ 的元素个数。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-100 \le a_i \le 100$），表示数组元素。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示依次执行两个操作后可能得到的最大数组和。

示例

输入：

8
3
-2 3 -3
1
0
2
0 1
1
-99
4
10 -2 -3 7
5
-1 -2 -3 -4 -5
6
-41 22 -69 73 -15 -50
12
1 2 3 4 5 6 7 8 9 10 11 12

输出：

8
0
1
99
22
15
270
78

样例解释

• 第一个测试用例：
  先重排为 $[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）。