Problem
Recientemente, Risotto Nero se enteró de las torres de Hanoi y le gustó mucho este rompecabezas. Sin embargo, se cansó de jugar en papel, por lo que decidió reproducirlos en la vida real.
Sin embargo, Risotto Nero solo tenía anillos del mismo radio, por lo que se le ocurrió un rompecabezas diferente.
Hay n palos. Inicialmente, cada uno de ellos tiene exactamente un anillo o ninguno. Al mismo tiempo, al menos un anillo está presente en cualquiera de los palos.
Con una acción, puedes transferir el anillo a una varita adyacente.
Es necesario que el número mínimo de acciones logre tal situación que algún número entero k > 1 tal que el número de anillos en cada uno de los palos sería divisible por k, o decir que esto es imposible.
Risotto Nero ya resolvió este problema y está esperando que verifique sus respuestas.
Entrada:
La primera línea contiene un único número entero n (1 ≤ n ≤ 10
5) — número de palos.
La segunda línea contiene n enteros a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — el número inicial de anillos en cada uno de los palos.
Salida:
Si la solución requerida no existe, escriba −1.
De lo contrario, imprima x — el número mínimo de acciones para llevar el rompecabezas al estado deseado.
Ejemplos:
| Entrada |
Salida |
3
1 0 1
| 2 |
1
1 |
-1 |
Explicación:
En el primer ejemplo, primero puede mover el anillo del tercer palo al segundo, luego del segundo al primero. Después de eso, el número de anillos en cada uno de los palos se dividirá por 2.