G. Macaron Conveyor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After a long day at CODEFEM, the organizers prepared several trays of macarons for the participants.

There are $$$N$$$ trays arranged from left to right on a conveyor belt. The $$$i$$$-th tray initially contains $$$a_i$$$ macarons.

The conveyor belt can only move macarons to the right. In one operation, you may choose a tray $$$i$$$ ($$$1 \le i \lt N$$$) that contains at least one macaron, and move exactly one macaron from tray $$$i$$$ to tray $$$i+1$$$.

The organizers want every tray to contain exactly the same number of macarons.

Determine whether this is possible.

If it is possible, print the minimum number of operations required to make all trays contain the same number of macarons.

Otherwise, print $$$-1$$$.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 100$$$), representing the number of trays.

The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le 10^4$$$), where $$$a_i$$$ is the number of macarons initially placed on the $$$i$$$-th tray.

Output

Print a single integer.

If it is possible to make every tray contain the same number of macarons, print the minimum number of operations required.

Otherwise, print $$$-1$$$.

Examples
Input
3
7 3 2
Output
5
Input
4
1 5 3 3
Output
-1
Input
5
2 2 2 2 2
Output
0
Note

Example 1.

In the first example, there are 12 macarons in total, so every tray must contain 4 macarons.

The trays initially contain 7, 3, and 2 macarons. Move 3 macarons from tray 1 to tray 2, then move 2 macarons from tray 2 to tray 3.

The total number of operations is 3 + 2 = 5.

Example 2.

In the second example, there are 12 macarons in total, so every tray would need to contain 3 macarons.

However, the first tray contains only 1 macaron. Since macarons can only move to the right, it is impossible to add macarons to the first tray.

Example 3.

In the third example, all trays already contain the same number of macarons, so the answer is 0.