Andrew and Stones
Contest: Codeforces Global Round 19
Difficulty rating: 1200
Tags: greedy, implementation

Andrew has $$$n$$$ piles with stones. The $$$i$$$-th pile contains $$$a_i$$$ stones. He wants to make his table clean so he decided to put every stone either to the $$$1$$$-st or the $$$n$$$-th pile.

Andrew can perform the following operation any number of times: choose $$$3$$$ indices $$$1 \le i < j < k \le n$$$, such that the $$$j$$$-th pile contains at least $$$2$$$ stones, then he takes $$$2$$$ stones from the pile $$$j$$$ and puts one stone into pile $$$i$$$ and one stone into pile $$$k$$$.

Tell Andrew what is the minimum number of operations needed to move all the stones to piles $$$1$$$ and $$$n$$$, or determine if it's impossible.

Input format:
The input contains several test cases. The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.

The first line for each test case contains one integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the length of the array.

The second line contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array elements.

It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case print the minimum number of operations needed to move stones to piles $$$1$$$ and $$$n$$$, or print $$$-1$$$ if it's impossible.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, it is optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 5)$$$. The array becomes equal to $$$[2, 0, 2, 3, 7]$$$.
2. Select $$$(i, j, k) = (1, 3, 4)$$$. The array becomes equal to $$$[3, 0, 0, 4, 7]$$$.
3. Twice select $$$(i, j, k) = (1, 4, 5)$$$. The array becomes equal to $$$[5, 0, 0, 0, 9]$$$. This array satisfy the statement, because every stone is moved to piles $$$1$$$ and $$$5$$$.

In the second test case, it's impossible to put all stones into piles with numbers $$$1$$$ and $$$3$$$:

1. At the beginning there's only one possible operation with $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 1, 2]$$$.
2. Now there is no possible operation and the array doesn't satisfy the statement, so the answer is $$$-1$$$.

In the third test case, it's optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 0, 2]$$$. This array satisfies the statement, because every stone is moved to piles $$$1$$$ and $$$3$$$.

In the fourth test case, it's impossible to do any operation, and the array doesn't satisfy the statement, so the answer is $$$-1$$$.

Example input:
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2

Example output:
4
-1
1
-1

Editorial:
Consider $$$2$$$ cases when the answer is $$$-1$$$ for sure:
1. For all $$$1 < i < n$$$: $$$a_i = 1$$$. In this case, it's not possible to make any operation and not all stones are in piles $$$1$$$ or $$$n$$$.
2. $$$n = 3$$$ and $$$a_2$$$ is odd. Then after any operation this number will remain odd, so it can never become equal to $$$0$$$.
Later it will become clear why these are the only cases where the answer is $$$-1$$$. To show it consider the following algorithm:
1. If all stones are in piles $$$1$$$ and $$$n$$$ then the algorithm is done.
2. If there is at least one non-zero even element (piles $$$1$$$ and $$$n$$$ don't count), then subtract $$$2$$$ from it, add $$$1$$$ to the odd number to the left or to the pile $$$1$$$ if there's no such number. Similarly add $$$1$$$ to the odd number to the right or to the pile $$$n$$$ if there's no such number. Then continue the algorithm. Note that the number of odd elements after it (piles $$$1$$$ and $$$n$$$ don't count) decreases at least by $$$1$$$ (if there was any odd number). Also either a new even number has appeared, or the algorithm will be done.
3. If all remaining non-zero numbers are odd, then there is at least one odd number greater than $$$1$$$. So let's subtract $$$2$$$ from this element and add ones similar to the $$$2$$$-nd case. In this case the number of odd elements decreases at least by $$$1$$$.
From the notes written in the second and third cases, it follows that the algorithm always puts all stones to the piles $$$1$$$ and $$$n$$$. Also note that if in the initial array the element in position $$$i$$$ ($$$1 < i < n$$$) was even, then the algorithm did not add any $$$1$$$ to it, so the number of operations with the center in $$$i$$$ equals to $$$\frac{a_i}{2}$$$. And if $$$a_i$$$ was odd, the algorithm will add $$$1$$$ to this element exactly once, so the number of operations with the center in $$$i$$$ equals to $$$\frac{a_i + 1}{2}$$$.
This algorithm is optimal because for each odd number it's necessary to add at least $$$1$$$ to it and the algorithm adds exactly $$$1$$$. And from even elements the algorithm can only subtract. It means that the answer to the problem equals to $$$\sum_{i=2}^{n-1} \lceil \frac{a_i}{2} \rceil$$$. Time complexity is $$$O(n)$$$.