题目描述

Farmer John 的草地里的草在一场大旱中都干死了。

经过数小时的绝望和沉思，Farmer John 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。

FJ 的 $N$ 头奶牛排成一行，队伍中的第 $i$ 头奶牛的饥饿度为 $h_i$。

由于奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 $i$ 和 $i+1$ 并分别喂她们一袋玉米，令她们的饥饿度各减少 $1$。

FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。

请帮助 FJ 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 $-1$。

输入格式（dry.in）

每个测试用例包含多个独立的子测试用例，必须全部回答正确才能通过整个测试用例。

输入的第一行包含 $T$ $(1 <= T <= 100)$，为你需要求解的子测试用例的数量。

以下是 $T$ 个子测试用例，每个子测试用例包含两行。

第一行包含 $N$，第二行包含 $h_1,h_2,...,h_n$。输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。每个子测试用例的 $N$ 的值可能不同。

输出格式（dry.out）

输出 $T$ 行，每个测试用例输出一行。

样例

输入样例

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

样例提示

对于第一个子测试用例，给奶牛 $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$ 没有额外限制。