题目内容

小明面前有一排 $n$ 个魔法水晶，第 $i$ 个水晶带有一个整数能量值 $a_i$，可能为正、负或零。

他可以任意次施展同一种法术：选择一个下标 $i$（$1 \le i < n$），让第 $i$ 个和第 $i+1$ 个水晶的能量值同时变为自身的相反数（即 $a_i \leftarrow -a_i$，$a_{i+1} \leftarrow -a_{i+1}$）。

小明希望经过若干次法术后，所有水晶的能量总和尽可能大。请你帮他计算能够达到的最大总和。

数据范围与约定：

• 测试数据组数 $T$ 满足 $1 \le T \le 10^4$；
• 对于每组数据，水晶个数 $n$ 满足 $1 \le n \le 2 \times 10^5$，每个能量值的绝对值均不超过 $10^9$；
• 所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据组数。 接下来对于每组测试数据： 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示水晶的个数； 第二行包含 $n$ 个整数，表示初始能量值 $a_1, a_2, \dots, a_n$，相邻整数之间由空格分隔，每个整数的绝对值不超过 $10^9$。 题目保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行，包含一个整数，表示经过若干次法术后所有水晶能量总和的最大值。

样例1

输入

3
1
5
1
-3
1
0

输出

5
-3
0

说明

每组数据只有 1 个水晶（$n = 1$），无法执行任何法术。因此最终总和等于该水晶自身的能量值： 第一组：$5$； 第二组：$-3$； 第三组：$0$。

在本题算法的角度，第一组负数个数为偶数（0 个），绝对值之和 $5$；第二组负数个数为奇数（1 个），绝对值之和 $3$，最小绝对值为 $3$，结果为 $3 - 2 \times 3 = -3$；第三组包含 0，负数个数为偶数，结果为 $0$。

样例2

输入

1
4
-1 -2 3 4

输出

10

说明

初始数组为 $-1, -2, 3, 4$，负数个数为 2（偶数）。根据结论，可以经过若干次法术将所有数变为非负数。 例如：对下标 $1$（$-1$ 和 $-2$）施展法术，数组变为 $1, 2, 3, 4$，总和为 $1 + 2 + 3 + 4 = 10$。 绝对值之和 $1 + 2 + 3 + 4 = 10$，负数个数偶数，直接输出 $10$。

样例3

输入

1
5
-1 -2 3 -4 5

输出

13

说明

初始数组为 $-1, -2, 3, -4, 5$，负数个数为 3（奇数）。此时无法让所有数变为非负数，必须保留一个数的符号为负。为了使总和最大，保留绝对值最小的那个负数不变，其余负数变为正数。 绝对值最小的是 $-1$（绝对值 $1$）。将 $-2$ 和 $-4$ 通过法术变正，最终数组可变为 $-1, 2, 3, 4, 5$，总和为 $-1 + 2 + 3 + 4 + 5 = 13$。 按公式：绝对值之和 $1 + 2 + 3 + 4 + 5 = 15$，最小绝对值为 $1$，结果 $15 - 2 \times 1 = 13$。

样例4

输入

1
3
-2 0 3

输出

5

说明

初始数组为 $-2, 0, 3$，负数个数为 1（奇数）。最小绝对值为 $0$（来自元素 0）。 可以保留 $0$ 为负数（$0$ 的正负不影响值），将 $-2$ 变为正数，最终数组为 $2, 0, 3$，总和 $5$。 按公式：绝对值之和 $2 + 0 + 3 = 5$，最小绝对值 $0$，结果 $5 - 2 \times 0 = 5$。