Farmer John 的草地里的草在一场大旱中都干死了。
经过数小时的绝望和沉思，Farmer John 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。
FJ 的 N 头奶牛排成一行，队伍中的第 i 头奶牛的饥饿度为 hi。
由于奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 i 和 i+1 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。
FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。
请帮助 FJ 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 −1。
5 3 8 10 5 6 4 6 4 4 6 4 3 0 1 0 2 1 2 3 10 9 9
14 16 -1 -1 -1
数据范围 1≤T≤100, 1≤N≤105, 0≤hi≤109, 所有子测试用例的 N 之和不超过 105。 每个子测试用例的 N 的值可能不同。 样例解释 对于第一个子测试用例，给奶牛 2 和 3 各两袋玉米，然后给奶牛 1 和 2 各五袋玉米，可以使得所有奶牛的饥饿度均为 3。 对于第二个子测试用例，给奶牛 1 和 2 各两袋玉米，奶牛 2 和 3 各两袋玉米，奶牛 4 和 5 各两袋玉米，奶牛 5 和 6 各两袋玉米，可以使得所有奶牛的饥饿度均为 2。 对于余下的子测试用例，均不可能使得奶牛们的饥饿度相等。
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 914
16
-1
-1
-1