You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

输入格式

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

输入的第一行包含 $T$（$1\le T\le 100$），为你需要求解的子测试用例的数量。

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

第一行包含 $N$，第二行包含 $h_1,h_2,\ldots,h_N$。输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。

每个子测试用例的 $N$ 的值可能不同。

输出格式

输出 $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 \leq 3$ 以及 $h_i\le 100$。

• 测试点 3-8 的所有子测试用例满足 $N\le 100$ 以及 $h_i\le 100$。

• 测试点 9-14 的所有子测试用例满足 $N\le 100$。

• 测试点 15 没有额外限制。

• 此外，测试点 3-5 和 9-11 中的 $N$ 均为偶数，测试点 6-8 和 12-14 中的 $N$ 均为奇数。