Codeforces Round 1131 (Div. 3) E. Swap and Negate

E. Swap and Negate

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given an array $a$ of length $n$ .

You are allowed to perform the following operation on the array $a$ any number of times (including zero):

Choose an index $i$ such that $1 \le i \lt n$ ;
Set $a_i := -a_{i+1}$ and $a_{i+1} := -a_i$ simultaneously.

Determine the maximum possible sum of all elements in the array that can be achieved by performing the operations optimally.

Input

The first line of the input contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The description of each test case follows.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 2\cdot10^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 \le a_i \le 10^9$ ) — the elements of the array $a$ .

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

Output

For each test case, print a single integer — the maximum possible sum of the array elements after performing the operations any number of times.

Example

Input

4
1
-3
4
1 -2 -3 4
5
-10 1 0 1 -10
2
6 -7

Output

Note

For the first test case, no operation can be performed. Hence, the maximum sum will be equal to $-3$ .

For the second test case, choosing $i = 2$ makes the array $a = [1, 3, 2, 4]$ . Now, the sum of all the elements is equal to $10$ . It can be shown that this is the maximum possible.

我们抛开复杂的数学术语，用最直观的视角（追踪某一个具体数字的移动）一步一步来看这道题。

第一步：观察单个数字在“移动”时发生了什么

题目允许的操作是：选相邻的两个数 $a_i, a_{i+1}$ ，变成 $-a_{i+1}, -a_i$ 。

我们只盯住某一个特定的数字 $x$ 。
假设它现在在某个位置上：

如果它和右边的数操作一次：它跑到了右边，值变成了 $-x$ 。
如果它和左边的数操作一次：它跑到了左边，值也变成了 $-x$ 。

关键结论 1：

任何一个数字，只要向左或向右走 1 步，它的正负号就会翻转一次（乘 $-1$ ）。

那么：

走 $1$ 步：变成负的（ $\times -1$ ）
走 $2$ 步：负负得正，变回原来的符号（ $\times 1$ ）
走 $3$ 步：又变负（ $\times -1$ ）
……
只要移动的步数是奇数，符号就变成相反的；只要移动的步数是偶数，符号就保持不变。

第二步：数字的最终值由什么决定？

为了方便，我们把下标统一设为从 $0$ 开始： $0, 1, 2, \dots, n-1$ 。

假设某个数字原来在下标 $i$ （比如 $a_i$ ），经过若干次移动后，最终落在了下标 $j$ ：

它走过的步数与 $(j - i)$ 的奇偶性是一样的。
所以它最终的值一定是：
$\text{最终值} = a_i \times (-1)^{j - i}$

利用初中数学知识： $(-1)^{j - i} = (-1)^j \times (-1)^{-i} = (-1)^j \times (-1)^i$ 。
我们把它重新组合一下：
$\text{最终值} = \underbrace{[a_i \times (-1)^i]}_{\text{只跟原数字和初始位置有关}} \times \underbrace{(-1)^j}_{\text{只跟最终落在哪有关}}$

我们把前面那一坨起个名字，叫 $c_i$ ：
$c_i = a_i \times (-1)^i$

如果初始下标 $i$ 是偶数（0, 2, 4…）： $c_i = a_i$
如果初始下标 $i$ 是奇数（1, 3, 5…）： $c_i = -a_i$

那么，这个数落在位置 $j$ 时，对总和的贡献就是：
$\text{最终贡献} = c_i \times (-1)^j$

第三步：把数组看成一排“有符号的坑位”

我们最终要得到 $n$ 个位置（下标 $0$ 到 $n-1$ ）。
每个位置 $j$ 决定了放入其中的数是乘以 $+1$ 还是 $-1$ ：

偶数下标的位置（0, 2, 4…）： $(-1)^j = +1$ ，所以谁放进来，就加上谁的 $c_i$ 。
奇数下标的位置（1, 3, 5…）： $(-1)^j = -1$ ，所以谁放进来，就减去谁的 $c_i$ 。

也就是说，这个数组其实相当于有两类“坑位”：

加号坑位（偶数下标）：共有 $\lceil n/2 \rceil$ 个（即 (n + 1) / 2 个）。
减号坑位（奇数下标）：共有 $\lfloor n/2 \rfloor$ 个（即 n / 2 个）。

第四步：我们可以自由安排谁去哪个坑位吗？

可以！
因为冒泡排序告诉我们：只通过“交换相邻两个元素”，可以排出任意你想要的顺序（全排列）。
换句话说，你可以随心所欲地把这 $n$ 个数分配到这 $n$ 个坑位里。

现在问题就彻底变成了一个小学贪心问题：

你手里有 $n$ 个计算好的数字 $c_0, c_1, \dots, c_{n-1}$ 。
面前有：

$\lceil n/2 \rceil$ 个加号坑位

$\lfloor n/2 \rfloor$ 个减号坑位

怎样放能让总和最大？

答案显而易见：

把最大的那些 $c_i$ 放进“加号坑位”；
把最小的那些 $c_i$ 放进“减号坑位”。

第五步：手算一个样例感受一下

以样例 2 为例：
n = 4，数组为 [1, -2, -3, 4]

1. 下标从 0 开始算 $c_i$ ：

$i=0$ （偶数）： $c_0 = a_0 = 1$
$i=1$ （奇数）： $c_1 = -a_1 = -(-2) = 2$
$i=2$ （偶数）： $c_2 = a_2 = -3$
$i=3$ （奇数）： $c_3 = -a_3 = -4$

算出来的 $c$ 数组为：[1, 2, -3, -4]。

2. 统计坑位：

$n = 4$ ，偶数下标有 $0, 2$ （共 2 个加号坑位）。
奇数下标有 $1, 3$ （共 2 个减号坑位）。

3. 贪心分配：

把 $c$ 排序：[-4, -3, 1, 2]
最大的 2 个数（1, 2）放加号坑位： $+1 + 2 = 3$
最小的 2 个数（-4, -3）放减号坑位： $-(-4) - (-3) = 4 + 3 = 7$
最大总和 = $3 + 7 = 10$ 。

这与样例输出的 10 完全一致！

总结

整个做法其实只有三句话：

每个元素根据原下标的奇偶性计算出 $c_i$ （偶不变，奇取反）。
把 $c$ 数组排序。
最小的 $\lfloor n/2 \rfloor$ 个数取负号，其余较大的数取正号，加起来就是答案。