CF1778A.Flip Flop Sum

You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$. The integers are either $1$ or $-1$. You have to perform the following operation exactly once on the array $a$:

• Choose an index $i$ ($1 \leq i \lt n$) and flip the signs of $a_i$ and $a_{i+1}$. Here, flipping the sign means $-1$ will be $1$ and $1$ will be $-1$.

What is the maximum possible value of $a_1 + a_2 + \ldots + a_n$ after applying the above operation?

给你一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$，其中每个整数均为 $1$ 或 $-1$。你必须在数组 $a$ 上恰好执行一次如下操作：

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

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

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$), the length of the array $a$.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i = 1$ or $a_i = -1$).

The sum of $n$ over all cases doesn't exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

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

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

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

For each test case, print the maximum possible sum of the array $a$ you can get in a separate line.

对于每个测试用例，在单独的一行中输出你能得到的数组 $a$ 的最大可能和。

In the first case, we can choose index $4$ and flip the signs of $a_4$ and $a_5$. After this operation, the sum will be $-1+1+1+1+1 = 3$. We can't make the sum larger than this.

In the third case, the only option is to choose the index $1$.

在第一种情况下，我们可以选择索引 $4$，并翻转 $a_4$ 和 $a_5$ 的符号。执行此操作后，和为 $-1+1+1+1+1 = 3$。我们无法使和大于该值。

在第三种情况下，唯一可选的索引是 $1$。