Problem Statement

You are given a length-$N$ integer sequence $A=(A_1,A_2,\dots,A_N)$. You can perform the following operation on $A$ any number of times.

• Choose an integer $i$ with $1 \leq i \leq N$. For every integer $j$ that is a positive divisor of $i$, add $1$ to $A_j$.

Determine whether it is possible to make all elements of $A$ equal, and if it is possible, find the minimum number of operations required to do so.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$
• $A_1$ $A_2$ $\dots$ $A_N$

Output

If it is possible to make all elements of $A$ equal, output, in one line, the minimum number of operations required to do so; otherwise, output $-1$.

3
4 7 4

3

If you choose $i=3$ for the first operation, you get $A=(5,7,5)$. If you choose $i=3$ for the second operation, you get $A=(6,7,6)$. If you choose $i=3$ for the third operation, you get $A=(7,7,7)$. It is impossible to make all elements of $A$ equal with fewer than three operations, so the answer is $3$.

5
1 3 4 5 6

5

2
5 2

-1

• Source: AtCoder ABC 474 F