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 \leq x < N~ y restarle ~1~ a ~A_x~ y sumarle ~1~ a ~A_{x+1}~.

-Seleccionar un número ~x~, tal que ~1 < x \leq 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 \leq N \leq 10^5~, ~0 \leq A_i \leq 1~

Subtarea 2: (50 puntos) ~1 \leq N \leq 10^6~, ~0 \leq A_i \leq 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