乾旱使 Farmer John 牧場的草枯了。絕望思索數小時後，他想到買玉米餵珍愛的牛這個妙招。

$N$ 頭牛（$1\le N\le10^5$）排成行，第 $i$ 頭飢餓值 $h_i$（$0\le h_i\le10^9$）。牛愛社交堅持一起吃，所以唯一減飢方法是選相鄰 $i,i+1$，各餵一袋，各值減一。

FJ 要讓全部飢餓值相同且非負。求最少玉米袋數，不能則輸出 -1。

輸入格式

若干獨立組須全部正確解答。首行 $T$（$1\le T\le100$）。每組兩行先 $N$ 再 $h_1,h_2,\ldots,h_N$。所有 $N$ 總和最多 $10^5$，各組 $N$ 可不同。

輸出格式

輸出 $T$ 行，每組一行。

數值大，可能需 64 位整數，如 C/C++ long long。

範例

輸入格式 1

5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

輸出格式 1

14
16
-1
-1
-1

說明

首組給 2、3 各兩袋，再給 1、2 各五袋，最後各頭飢餓值 3。

第二組給 1、2 各兩袋，2、3 各兩袋，4、5 各兩袋，5、6 各兩袋，最後各值 2。

其餘組不能讓飢餓值相同。

子任務

• 輸入 2 全部組：$N\le3$ 且 $h_i\le100$。
• 輸入 3–8 全部組：$N\le100$ 且 $h_i\le100$。
• 輸入 9–14 全部組：$N\le100$。
• 輸入 15 無額外限制。

另，輸入 3–5、9–11 的 $N$ 恆偶數；6–8、12–14 恆奇數。

題目作者：Arpan Banerjee