题目描述

给定长度为n的序列a，其中a 1 ,a 2 ,a 3 ,...a n 只有 1 和 -1 两种取值

你必须进行一次操作，选择一个a i 使a i = -a i,a i+1 = -a i+1

求∑ i=1 n ​ (a i ​ )的最大值

输入说明

第一行一个正整数 T 表示有 T 组测试数据。

接下来每组测试数据：

第一行一个正整数 n 表示序列长度。

接下来一行 n 个数a 1 ,a 2 ,a 3 ,...a n

输出说明

对于每组测试数据，输出一行，表示 ∑ i=1 n ​ (a i ​ ) 的最大值

样例输入

4 
5 
-1 1 1 -1 -1 
5 
1 1 -1 -1 -1 
2 
1 1 
4 
1 -1 -1 1

样例输出

3 
3 
-2 
4

样例解释

对于第一组数据 -1 1 1 -1 -1

可以选择 -1,1 执行操作变成 1,-1 总和不变

选择-1,-1 执行一次操作变成1,1总和加2

由于最多只能执行一次 所以显然选择第二种操作使总和为3

对于第三组数据 因为全是 整数所以不需要执行操作 因此结果为2

数据范围

对于30%的数据 T = 1

对于60%的数据 T ≤ 100, n ≤ 10000

对于100%的数据 T ≤ 1000， 2 ≤ n ≤ 10^5， a i ∈ {-1,1},且一个测点所有组测试数据的 n 之和不超过 2e5