Addition

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence, add 1 to three adjacent values per operation to make the odd-position and even-position sums equal, then find the minimum operations or -1.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

You are given a sequence of integers $A_1, A_2, \cdots, A_N$ . You may repeat the following operation as many times as you want.

Increase three adjacent values by 1 each.

Use as few operations as possible to make the sum of the values at odd positions equal to the sum of the values at even positions. Find the minimum number of operations needed for the odd-position sum and the even-position sum to become equal. If they cannot be made equal, print -1.

Input

The first line contains the length $N$ of the sequence. ( $3 \le N \le 100000$ )

The second line contains the sequence $A_1, A_2, A_3, \cdots, A_N$ separated by spaces. ( $-100000 \le A_i \le 100000$ )

Output

Print the minimum number of operations needed to make the odd-position sum equal to the even-position sum. If it is impossible, print -1.

Examples5

Example 1
Input
```
4
1 1 1 1
```
Expected output
```
0
```
Example 2
Input
```
5
1 2 3 4 5
```
Expected output
```
3
```
Example 3
Input
```
5
2 1 2 1 2
```
Expected output
```
4
```
Example 4
Input
```
3
0 1 0
```
Expected output
```
1
```
Example 5
Input
```
3
1 0 1
```
Expected output
```
-1
```