本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

由于干旱，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$ 行，每行对应一个测试用例。

注意，本题涉及的整数可能很大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

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$。 对于其余测试用例，不可能使奶牛的饥饿值相等。 SCORING: 输入 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$ 总是奇数。 Problem credits: Arpan Banerjee

来源

USACO|2022|Bronze