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 個整數(shù) a1,a2,…,an 組成的數(shù)組。 整數(shù)為 1 或 -1。 您必須對數(shù)組 a 執(zhí)行一次以下操作：

選擇一個索引 i (1≤i<n) 并翻轉(zhuǎn) ai 和 ai+1 的符號。 這里，翻轉(zhuǎn)符號意味著-1將是1，1將是-1。

應(yīng)用上述運算后，a1+a2+…+an 的最大可能值是多少？

輸入

每個測試包含多個測試用例。 第一行包含測試用例的數(shù)量 t (1≤t≤500)。 測試用例的描述如下。

每個測試用例的第一行包含一個整數(shù)n（2≤n≤105），即數(shù)組a的長度。

下一行包含 n 個整數(shù) a1,a2,…,an（ai=1 或 ai=?1）。

所有案例的 n 總和不超過 105。

輸出

對于每個測試用例，打印數(shù)組 a 的最大可能和

? 你可以單獨排隊。

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

看是否有連續(xù)的負(fù)數(shù)，是否有負(fù)數(shù)，這兩個信息，然后給出對應(yīng)的值即可；

easy題目：

下面是代碼：