2172: 干旱
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：36
Solved：25
Description
Farmer Joℎn 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，Farmer Joℎn想到了一个 绝妙的主意，购买玉米来喂养他宝贵的奶牛。
Farmer Joℎn 的N(1 ≤ N ≤ 105) 头奶牛排成一行，队伍中的第 i 头奶牛的饥饿度为 ℎi (0 ≤ ℎi ≤ 109)。由于奶牛是社会性动物，她们坚持一起进食，Farmer Joℎn 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 i(1≤i < N) 和 i+1 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。
Farmer Joℎn 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。请帮助Farmer Joℎn 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 −1。
Farmer Joℎn 的N(1 ≤ N ≤ 105) 头奶牛排成一行，队伍中的第 i 头奶牛的饥饿度为 ℎi (0 ≤ ℎi ≤ 109)。由于奶牛是社会性动物，她们坚持一起进食，Farmer Joℎn 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 i(1≤i < N) 和 i+1 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。
Farmer Joℎn 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。请帮助Farmer Joℎn 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 −1。
Input
第一行包含 T(1≤ T≤100)，为你需要求解的子测试用例的数量。以下是 T 个子测试用例，每个子测试用例包含两行。
第一行包含N，表示奶牛的数量。
第二行包含 ℎ1, ℎ2, ⋯ , ℎN。
输入保证所有子测试用例的 N 之和不超过105。每个子测试用例的N的值可能不同。
第一行包含N，表示奶牛的数量。
第二行包含 ℎ1, ℎ2, ⋯ , ℎN。
输入保证所有子测试用例的 N 之和不超过105。每个子测试用例的N的值可能不同。
Output
输出T 行，每个测试用例输出一行。
Sample Input Copy
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9Sample Output Copy
14
16
-1
-1
-1HINT
【样例解释】
对于第一个子测试用例，给奶牛2 和 3 各两袋玉米，然后给奶牛1和 2 各五袋玉米，可以使得所有奶牛的饥饿度均为 3。
对于第二个子测试用例，给奶牛1 和 2 各两袋玉米，奶牛2和 3 各两袋玉米，奶牛 4 和 5 各两袋玉米， 奶牛 5 和 6各两袋玉米，可以使得所有奶牛的饥饿度均为 2。
对于余下的子测试用例，均不可能使得奶牛们的饥饿度相等。
【数据规模】
测试点 1-2 的所有子测试用例满足 N ≤ 3 以及 ℎi ≤ 100 。
测试点 3-8 的所有子测试用例满足 N ≤ 100 以及 ℎi ≤ 100。
测试点 9-14 的所有子测试用例满足 N ≤ 100。
测试点 15 没有额外限制。
此外，测试点3-5 和 9-11 中的 N 均为偶数，测试点6-8 和 12-14 中的 N 均为奇数。
对于第一个子测试用例，给奶牛2 和 3 各两袋玉米，然后给奶牛1和 2 各五袋玉米，可以使得所有奶牛的饥饿度均为 3。
对于第二个子测试用例，给奶牛1 和 2 各两袋玉米，奶牛2和 3 各两袋玉米，奶牛 4 和 5 各两袋玉米， 奶牛 5 和 6各两袋玉米，可以使得所有奶牛的饥饿度均为 2。
对于余下的子测试用例，均不可能使得奶牛们的饥饿度相等。
【数据规模】
测试点 1-2 的所有子测试用例满足 N ≤ 3 以及 ℎi ≤ 100 。
测试点 3-8 的所有子测试用例满足 N ≤ 100 以及 ℎi ≤ 100。
测试点 9-14 的所有子测试用例满足 N ≤ 100。
测试点 15 没有额外限制。
此外，测试点3-5 和 9-11 中的 N 均为偶数，测试点6-8 和 12-14 中的 N 均为奇数。