Dado un arreglo $A$, de $N$ elementos, indexados de $1$ a $N$, se puede realizar cualquiera de las siguientes operaciones cualquier número de veces, cada operación tiene costo $1$. Las operaciones son:

-Seleccionar un número $x$, tal que $1\le x<N$ y restarle $1$ a $A_x$ y sumarle $1$ a $A_{x+1}$.

-Seleccionar un número $x$, tal que $1<x\le N$ y restarle $1$ a $A_x$ y sumarle $1$ a $A_{x-1}$.

Diga el número mínimo de operaciones que se tienen que realizar para que exista un número $K(K>1)$ que divida a todos los números de $A$.

Entrada

Una línea con un entero, $N$. Una línea con $N$ enteros, el i-ésimo de ellos es $A_i$.

Salida

Un entero, la cantidad mínima de operaciones que se tienen que realizar para cumplir con la restricción, o -1 si es imposible de cumplir.

Subtareas

Subtarea 1: (50 puntos) $1\le N\le {10}^5$, $0\le A_i\le 1$

Subtarea 2: (50 puntos) $1\le N\le {10}^6$, $0\le A_i\le {10}^6$

Ejemplo #1 de Entrada

3
1 0 1

Ejemplo #1 de Salida

2

Ejemplo #2 de Entrada

3
4 8 5

Ejemplo #2 de Salida

9

Ejemplo #3 de Entrada

5
3 10 2 1 5

Ejemplo #3 de Salida

2

Ejemplo #4 de Entrada

1
1

Ejemplo #4 de Salida

-1