干旱让 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