Problem Description

The grass in Farmer John’s pasture has all dried up in a severe drought. After hours of despair and thinking, Farmer John comes up with a brilliant idea: buy corn to feed his precious cows.

FJ has $N$ cows ($1 \leq N \leq 10^5$) standing in a line. The $i$-th cow in the line has hunger level $h_i$ ($0 \leq h_i \leq 10^9$). Since cows are social animals, they insist on eating together. The only way for FJ to decrease the cows’ hunger levels is to choose two adjacent cows $i$ and $i+1$ and feed each of them one bag of corn, which decreases both of their hunger levels by $1$.

FJ wants to feed his cows until all cows have the same non-negative hunger level. Please help FJ find the minimum number of bags of corn needed to reach this state, or output $-1$ if it is impossible.

Input Format

Each test contains multiple independent subtasks, and all of them must be answered correctly to pass the entire test.

The first line of input contains $T$ ($1 \le T \le 100$), the number of subtasks you need to solve.

Then follow $T$ subtasks. Each subtask contains two lines.

The first line contains $N$, and the second line contains $h_1,h_2,\ldots,h_N$. The input guarantees that the sum of $N$ over all subtasks does not exceed $10^5$.

The value of $N$ may be different for each subtask.

Output Format

Output $T$ lines, one line for each subtask.

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

Hint

Sample Explanation.

For the first subtask, feed cows $2$ and $3$ two bags of corn each, then feed cows $1$ and $2$ five bags of corn each. This makes all cows have hunger level $3$.

For the second subtask, feed cows $1$ and $2$ two bags of corn each, cows $2$ and $3$ two bags each, cows $4$ and $5$ two bags each, and cows $5$ and $6$ two bags each. This makes all cows have hunger level $2$.

For the remaining subtasks, it is impossible to make the cows’ hunger levels equal.

Constraints.

• For all subtasks in test point 2, $N \leq 3$ and $h_i \le 100$.

• For all subtasks in test points 3-8, $N \le 100$ and $h_i \le 100$.

• For all subtasks in test points 9-14, $N \le 100$.

• Test point 15 has no additional constraints.

• In addition, in test points 3-5 and 9-11, $N$ is even, and in test points 6-8 and 12-14, $N$ is odd.

Translated by ChatGPT 5