题目描述
认真写题的danm正在看一道相反数的题，路过的人机看到了题面瞅了瞅同时读了出来。
给定一个由 $n$ 个元素组成的数组 $a$ ，求数组在执行下列操作不限次数后的最大可能和。
这里最大和的意思时：从第一项到最后一项的和。
- 选择 $2$ 个相邻的个元素，翻转它们的符号。换句话说，选择 $i$ 这样的索引 $1 \leq i \leq n - 1$ ，并赋值 $a_i = -a_i$ 和 $a_{i+1} = -a_{i+1}$ 。
人机看完后觉得这个danm就是逊啦！这题难道不一眼秒。
人机：
danm：
给定一个由 $n$ 个元素组成的数组 $a$ ，求数组在执行下列操作不限次数后的最大可能和。
这里最大和的意思时：从第一项到最后一项的和。
- 选择 $2$ 个相邻的个元素，翻转它们的符号。换句话说，选择 $i$ 这样的索引 $1 \leq i \leq n - 1$ ，并赋值 $a_i = -a_i$ 和 $a_{i+1} = -a_{i+1}$ 。
人机看完后觉得这个danm就是逊啦！这题难道不一眼秒。
人机：
danm：输入
输入由多个测试用例组成。第一行包含一个整数 $t$ ( $1 \leq t \leq 1000$ ) - 测试用例的数量。测试用例说明如下。
每个测试用例的第一行都包含一个整数 $n$ ( $2 \leq n \leq 2\cdot10^5$ )( $2 \leq n \leq 2\cdot10^5$ ) - 数组的长度。
下一行包含 $n$ 个空格分隔的整数 $a_1,a_2,\dots,a_n$ （ $-10^9 \leq a_i \leq 10^9$ ）。( $-10^9 \leq a_i \leq 10^9$ ).
保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$ 。
每个测试用例的第一行都包含一个整数 $n$ ( $2 \leq n \leq 2\cdot10^5$ )( $2 \leq n \leq 2\cdot10^5$ ) - 数组的长度。
下一行包含 $n$ 个空格分隔的整数 $a_1,a_2,\dots,a_n$ （ $-10^9 \leq a_i \leq 10^9$ ）。( $-10^9 \leq a_i \leq 10^9$ ).
保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$ 。
输出
对于每个测试用例，输出数组在执行所述操作任意次数后可能具有的最大和。
样例输入 Copy
5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1
样例输出 Copy
1
13
6
39
2