P8092 [USACO22JAN] Drought B

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.

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 $T$ lines, one line for each subtask.

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