题目背景

原题为 P8092 [USACO22JAN] Drought B

题目描述

Gooby 在退休以后开始种地。但是好巧不巧，今年是大旱之年。经过0.1秒的绝望和沉思之后，Gooby 想到了一个绝妙的主意，他可以去购买农夫三拳来灌溉已经干旱的地。

Gooby 的农田可以看作 $N$ （$1 \leq N \leq 10^5$）块长度为 $1$ 的地皮排成一排。 其中第 $i$ 块地皮的干旱程度为 $h_i$（$0 \leq h_i \leq 10^9$）。由于 Gooby 能力有限，他一次操作中可以给两块相邻的地皮 $i$ 和 $i+1$ 同时浇灌，每块地皮花费 $1$ 瓶农夫三拳，使它们的干旱程度各减少 $1$。

Gooby 想将他的所有地皮灌溉到都具有相同的非负干旱程度。请帮助 Gooby 求出他达到上述状态所需的最少农夫三拳数。如果不可能达到，输出 $-1$。

输入格式

输入的第一行包含 $T$（$1\le T\le 100$），表示有 $T$ 组测试数据。

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

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

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

输出格式

输出 $T$ 行，每个测试用例输出一行，表示需要用的最少农夫三拳数，或者输出 $-1$ 表示做不到。

输入输出样例 #1

输入 #1

5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

输出 #1

14
16
-1
-1
-1

说明/提示

【样例解释】

对于第一个子测试用例，给地皮 $2$ 和 $3$ 各 $2$ 瓶农夫三拳，然后给地皮 $1$ 和 $2$ 各 $5$ 瓶农夫三拳，可以使得所有地皮的干旱程度均为 $3$。

对于第二个子测试用例，给地皮 $1$ 和 $2$ 各 $2$ 瓶农夫三拳，地皮 $2$ 和 $3$ 各 $2$ 瓶农夫三拳，地皮 $4$ 和 $5$ 各 $2$ 瓶农夫三拳，地皮 $5$ 和 $6$ 各 $2$ 瓶农夫三拳，可以使得所有地皮的干旱程度均为 $2$。

对于余下的测试用例，均不可能使得所有的地皮的干旱程度相等。

【数据范围】

• 测试点 $1-2$ 的所有子测试用例满足 $N \leq 10$ 以及 $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$ 均为奇数。