CF1791E.Negatives and Positives

Given an array $a$ consisting of $n$ elements, find the maximum possible sum the array can have after performing the following operation any number of times:

• Choose $2$ adjacent elements and flip both of their signs. In other words choose an index $i$ such that $1 \leq i \leq n - 1$ and assign $a_i = -a_i$ and $a_{i+1} = -a_{i+1}$.

给定一个包含 $n$ 个元素的数组 $a$，求对该数组执行以下操作任意次后所能得到的最大可能和：

• 选择两个相邻元素，并同时翻转它们的符号。换言之，选择一个下标 $i$（满足 $1 \leq i \leq n - 1$），并令 $a_i = -a_i$ 且 $a_{i+1} = -a_{i+1}$。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot10^5$) — the length of the array.

The following line contains $n$ space-separated integers $a_1,a_2,\dots,a_n$ ($-10^9 \leq a_i \leq 10^9$).

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

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

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2\cdot10^5$），表示数组的长度。

接下来的一行包含 $n$ 个以空格分隔的整数 $a_1,a_2,\dots,a_n$（$-10^9 \leq a_i \leq 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

For each test case, output the maximum possible sum the array can have after performing the described operation any number of times.

对于每个测试用例，输出在执行所述操作任意次数后，数组所能达到的最大可能和。

For the first test case, by performing the operation on the first two elements, we can change the array from $[-1, -1, -1]$ to $[1, 1, -1]$, and it can be proven this array obtains the maximum possible sum which is $1 + 1 + (-1) = 1$.

For the second test case, by performing the operation on $-5$ and $0$, we change the array from $[1, 5, -5, 0, 2]$ to $[1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2]$, which has the maximum sum since all elements are non-negative. So, the answer is $1 + 5 + 5 + 0 + 2 = 13$.

For the third test case, the array already contains only positive numbers, so performing operations is unnecessary. The answer is just the sum of the whole array, which is $1 + 2 + 3 = 6$.

对于第一个测试用例，对前两个元素执行操作后，数组可以从 $[-1, -1, -1]$ 变为 $[1, 1, -1]$，可以证明该数组达到了可能的最大和，即 $1 + 1 + (-1) = 1$。

对于第二个测试用例，对 $-5$ 和 $0$ 执行操作后，数组从 $[1, 5, -5, 0, 2]$ 变为 $[1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2]$，此时所有元素均非负，因此该数组具有最大和。故答案为 $1 + 5 + 5 + 0 + 2 = 13$。

对于第三个测试用例，数组中已全部为正数，因此无需执行任何操作。答案即为整个数组的和：$1 + 2 + 3 = 6$。