给定一个包含 n 个元素的数组 a。你可以执行任意多次以下操作,求数组元素之和的最大可能值:
选择两个相邻的元素,并将它们的符号同时取反。
换句话说,选择一个下标 i(1 \le i \le n-1),令 a_i=-a_i 且 a_{i+1}=-a_{i+1}。
输入包含多组测试数据。第一行包含一个整数 t(1 \le t \le 1000),表示测试数据的组数。接下来是 t 组测试数据。
每组测试数据的第一行包含一个整数 n(2 \le n \le 2 \cdot 10^5),表示数组的长度。
第二行包含 n 个用空格隔开的整数
a_1,a_2,\ldots,a_n(-10^9 \le a_i \le 10^9)。
保证所有测试数据的 n 之和不超过 2 \cdot 10^5。
对于每组测试数据,输出一个整数 S,表示在执行任意多次上述操作后,数组元素之和的最大可能值。每组输出占一行。
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
1 13 6 39 2
【数据范围】
1 \le t \le 1000;
2 \le n \le 2 \cdot 10^5;
-10^9 \le a_i \le 10^9;
所有测试数据的 n 之和不超过 2 \cdot 10^5;
输出答案 S 满足 -2 \cdot 10^{14} \le S \le 2 \cdot 10^{14}。
【样例说明】
在第一组样例中,对前两个元素进行操作,可以将数组从 [-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=13。
在第三组样例中,数组只包含正数,因此不需要执行任何操作。答案就是整个数组的和,即 1+2+3=6。