Problem
Recently, Risotto Nero found out about the towers of Hanoi, and he really liked this puzzle. However, he got tired of playing on paper, so he decided to reproduce them in real life.
However, Risotto Nero only had rings of the same radius, so he came up with a different puzzle.
There are n sticks. Initially, each of them either has exactly one ring, or none. At the same time, at least one ring is present on any of the sticks.
With one action, you can transfer the ring to an adjacent wand.
It is necessary for the minimum number of actions to achieve such a situation that some integer k > 1 such that the number of rings on each of the sticks would be divisible by k, or say that this is impossible.
Risotto Nero has already solved this problem and is waiting for you to check your answers.
Input:
The first line contains a single integer n (1 ≤ n ≤ 10
5) — number of sticks.
The second line contains n integers a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — the initial number of rings on each of the sticks.
Output:
If the required solution does not exist, print −1.
Otherwise print x — the minimum number of actions to bring the puzzle to the desired state.
Examples:
| Input |
Output |
3
1 0 1
| 2 |
1
1 |
-1 |
Explanation:
In the first example, you can first move the ring from the third stick to the second, then from the second to the first. After that, the number of rings on each of the sticks will be divided by 2.