242050 - 负号与正号

题目描述

给定一个包含 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。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 1 枚
难度 入门


上一题 下一题