CF 1778A - Flip Flop Sum

You are given an array of n integers a1,a2,…,an. 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≤i<n) and flip the signs of ai and ai+1. Here, flipping the sign means −1 will be 1 and 1 will be −1.

What is the maximum possible value of a1+a2+…+an after applying the above operation?

Input

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

The first line of each test case contains a single integer n (2≤n≤105), the length of the array a.

The next line contains n integers a1,a2,…,an (ai=1 or ai=−1).

The sum of n over all cases doesn't exceed 105.

Output

For each test case, print the maximum possible sum of the array a

 you can get in a separate line.

-------------------------------------

给定一个由 n 个整数 a1,a2,…,an 组成的数组。 整数为 1 或 -1。 您必须对数组 a 执行一次以下操作：

选择一个索引 i (1≤i<n) 并翻转 ai 和 ai+1 的符号。 这里，翻转符号意味着-1将是1，1将是-1。

应用上述运算后，a1+a2+…+an 的最大可能值是多少？

输入

每个测试包含多个测试用例。 第一行包含测试用例的数量 t (1≤t≤500)。 测试用例的描述如下。

每个测试用例的第一行包含一个整数n（2≤n≤105），即数组a的长度。

下一行包含 n 个整数 a1,a2,…,an（ai=1 或 ai=−1）。

所有案例的 n 总和不超过 105。

输出

对于每个测试用例，打印数组 a 的最大可能和

  你可以单独排队。

------------------------------------------------

看是否有连续的负数，是否有负数，这两个信息，然后给出对应的值即可；

easy题目：

下面是代码：