Description

You are given an integer sequence $a$ of length $n$.

You can perform the following operations any number of times (possibly, zero):

Select indices $1 \le i, j \le n$ such that $i \ne j$, and perform the operation: $a_i \leftarrow a_i + 1$, $a_j \leftarrow a_j - 1$ simultaneously.

Your task is to compute the minimum number of operations needed to make the sum of the prefix sums of $a$ equal to the sum of the suffix sums of $a$.

That is, let $s_i=a_1+a_2+\dots+a_i,t_i=a_i+a_{i+1}+\dots+a_n$, you need to make $s_1+s_2+\dots+s_n$ equal to $t_1+t_2+\dots+t_n$.

Note that $a_i$ can become negative after several operations.

Input Format

The first line contains a single integer $n$.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

Output Format

Print a single integer — the minimum number of operations needed.

If it is impossible to satisfy the condition within $10^{100}$ operations, print $-1$.

5
1 2 3 4 5

3

6
2 3 7 4 5 8

-1

Hint

This problem has subtasks.

• Subtask 1 (30 points): $1 \le n \le 2$
• Subtask 2 (30 points): $a_i = i$
• Subtask 3 (5 points): $a_i = 1$
• Subtask 4 (35 points): No additional constraints

It is guaranteed that for all testcases, $1 \le n,a_i \le 10^6$.