题目描述

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$，其中每个整数都是 $1$ 或 $-1$。你需要对数组 $a$ 执行如下操作恰好一次：

• 选择一个下标 $i$（$1 \leq i < n$），将 $a_i$ 和 $a_{i+1}$ 的符号翻转。这里，符号翻转指的是 $-1$ 变为 $1$，$1$ 变为 $-1$。

请问，执行上述操作后，$a_1 + a_2 + \ldots + a_n$ 的最大可能值是多少？

输入格式

每个测试点包含多个测试用例。第一行包含测试用例个数 $t$（$1 \leq t \leq 500$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示数组 $a$ 的长度。

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$a_i = 1$ 或 $a_i = -1$）。

所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，表示你能获得的数组 $a$ 的最大可能和。每个测试用例输出一行。

说明/提示

在第一个用例中，我们可以选择下标 $4$，翻转 $a_4$ 和 $a_5$ 的符号。操作后，数组变为 $-1, 1, 1, 1, 1$，此时和为 $3$。无法得到更大的和。

在第三个用例中，唯一的选择是选择下标 $1$。

由 ChatGPT 4.1 翻译

样例

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