A31323.摇摇晃摇

给你一个由 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 组成的数组。这些整数不是 $1$ 就是 $-1$ 。你必须对数组 $a$ 执行一次以下操作：

• 选择一个索引 $i$ ( $1 \leq i \leq n$ )，然后翻转 $a_i$ 和 $a_{i+1}$ 的符号。翻转符号会将数值从$-1$ 变为 $1$ 或者将 $1$ 变为 $-1$ 。

进行上述运算后， $a_1 + a_2 + \ldots + a_n$ 的最大值是多少？

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 。

对于每个测试用例，单独一行打印数组 $a$ 的最大总和。

在第一种情况下，我们可以选择索引 $4$ ，然后翻转 $a_4$ 和 $a_5$ 的符号。操作完成后，总和为 $-1+1+1+1+1 = 3$ 。

在第三种情况下，我们只能选择索引 $1$ 。