Equal Hunger Feeding

Farmer John has N cows in a row, where the i^th cow has hunger level \(h_i\) (with \(0 \le h_i \le 10^9\) and \(1 \le N \le 10^5\)). Due to a severe drought, the grass has all withered away, and Farmer John has decided to feed his cows with corn. However, the only method he has to reduce the hunger of his cows is as follows:

He may select two adjacent cows (say, cow \(i\) and cow \(i+1\)) and feed each one a bag of corn. Feeding a cow reduces its hunger level by \(1\) (i.e. \(h_i\) becomes \(h_i-1\)), and this operation costs 2 corn bags in total.

The cows are very social and always eat together. Farmer John wishes to feed them until they all have the same nonnegative hunger level. Note that since each operation reduces the hunger level of two consecutive cows by exactly 1, the difference between any two adjacent cows remains unchanged. Therefore, it is only possible to achieve equal hunger levels if the cows initially all have the same hunger level.

Your task is to determine the minimum number of corn bags required to make all the cows have the same nonnegative hunger level. If it is impossible to do so, output -1.

Observation: Since feeding two adjacent cows subtracts 1 from both, the difference between adjacent cows is invariant. Hence, if not all cows start with the same hunger level, it is impossible to equalize them.

Constraints:

• \(1 \le N \le 10^5\)
• \(0 \le h_i \le 10^9\)

inputFormat

The first line contains an integer \(N\), the number of cows. The second line contains \(N\) space-separated integers \(h_1, h_2, \dots, h_N\), where \(h_i\) denotes the hunger level of the \(i\)^th cow.

outputFormat

Output a single integer: the minimum number of corn bags required to make all cows have the same nonnegative hunger level. If it is impossible, output -1.

Note: If the cows already have equal hunger levels, no feeding is necessary and the answer is 0.

sample

3
5 5 5

0