A15705 | $Negatives and Positives$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Given an array $a$ consisting of $n$ elements, find the maximum possible sum the array can have after performing the following operation any number of times: - Choose $2$ adjacent elements and flip both of their signs. In other words choose an index $i$ such that $1 \leq i \leq n - 1$ and assign $a_i = -a_i$ and $a_{i+1} = -a_{i+1}$ .

The input consists of multiple test cases. The first line contains an integer $t$ ( $1 \leq t \leq 1000$ ) — the number of test cases. The descriptions of the test cases follow. The first line of each test case contains an integer $n$ ( $2 \leq n \leq 2\cdot10^5$ ) — the length of the array. The following line contains $n$ space-separated integers $a_1,a_2,\dots,a_n$ ( $-10^9 \leq a_i \leq 10^9$ ). It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$ .

For each test case, output the maximum possible sum the array can have after performing the described operation any number of times.

输入 #1

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

C++ 编辑器

输入

输出