#523. Drought B

Drought B

题目描述

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

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

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

输入格式

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

输入的第一行包含 TT1T1001\le T\le 100),为你需要求解的子测试用例的数量。

以下是 TT 个子测试用例,每个子测试用例包含两行。

第一行包含 NN,第二行包含 h1,h2,,hNh_1,h_2,\ldots,h_N。输入保证所有子测试用例的 NN 之和不超过 10510^5

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

输出格式

输出 TT 行,每个测试用例输出一行。

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

提示

【样例解释】

对于第一个子测试用例,给奶牛 2233 各两袋玉米,然后给奶牛 1122 各五袋玉米,可以使得所有奶牛的饥饿度均为 33

对于第二个子测试用例,给奶牛 1122 各两袋玉米,奶牛 2233 各两袋玉米,奶牛 4455 各两袋玉米,奶牛 5566 各两袋玉米,可以使得所有奶牛的饥饿度均为 22

对于余下的子测试用例,均不可能使得奶牛们的饥饿度相等。

【数据范围】

  • 测试点 2 的所有子测试用例满足 N3N \leq 3 以及 hi100h_i\le 100

  • 测试点 3-8 的所有子测试用例满足 N100N\le 100 以及 hi100h_i\le 100

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

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

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