时间限制：1秒　　内存限制：256M

---

【题目描述】

　　Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，Farmer John 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。

　　FJ 的 \(N（1≤N≤10^5）\) 头奶牛排成一行，队伍中的第 \(i\) 头奶牛的饥饿度为 \(h_i（0≤h_i≤10^9）\)。由于奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 \(i\) 和 \(i+1\) 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。

　　FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。请帮助 FJ 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 −1。

【输入格式】

　　每个测试用例包含多个独立的子测试用例，必须全部回答正确才能通过整个测试用例。输入的第一行包含\( T（1≤T≤100）\)，为你需要求解的子测试用例的数量。以下是 \(T\) 个子测试用例，每个子测试用例包含两行。第一行包含 \(N\)，第二行包含 \(h_1,h_2,…,h_N\)。输入保证所有子测试用例的 \(N\) 之和不超过 \(10^5\)。每个子测试用例的 \(N\) 的值可能不同。

【输出格式】

　　输出 \(T\) 行，每个测试用例输出一行。注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C 或 C++ 中的 "long long"）。

【输入输出样例】

　Input

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

　Output

14
16
-1
-1
-1

【样例解释】

　　于第一个子测试用例，给奶牛 2 和 3 各两袋玉米，然后给奶牛 1 和 2 各五袋玉米，可以使得所有奶牛的饥饿度均为 3。
　　对于第二个子测试用例，给奶牛 1 和 2 各两袋玉米，奶牛 2 和 3 各两袋玉米，奶牛 4 和 5 各两袋玉米，奶牛 5 和 6 各两袋玉米，可以使得所有奶牛的饥饿度均为 2。
　　对于余下的子测试用例，均不可能使得奶牛们的饥饿度相等。

【测试点性质】

　　• 测试点 \(2\) 的所有子测试用例满足 \(N≤3\) 以及 \(h_i≤100\)。
　　• 测试点 \(3-8\) 的所有子测试用例满足 \(N≤100\) 以及 \(h_i≤100\)。
　　• 测试点 \(9-14\) 的所有子测试用例满足 \(N≤100\)。
　　• 测试点 \(15\) 没有额外限制。
　　此外，测试点 \(3-5\) 和 \(9-11\) 中的 \(N\) 均为偶数，测试点 \(6-8\) 和 \(12-14\) 中的 \(N\) 均为奇数。

【来源】

　　Mr.he