Problem
Recentemente, o Risotto Nero descobriu as torres de Hanói e gostou muito desse quebra-cabeça. Porém, ele se cansou de brincar no papel e decidiu reproduzi-los na vida real.
No entanto, Risotto Nero só tinha anéis do mesmo raio, então ele criou um quebra-cabeça diferente.
Existem n palitos. Inicialmente, cada um deles tem exatamente um anel ou nenhum. Ao mesmo tempo, pelo menos um anel está presente em qualquer uma das varetas.
Com uma ação, você pode transferir o anel para uma varinha adjacente.
É necessário que o número mínimo de ações alcance tal situação que algum número inteiro k > 1 tal que o número de anéis em cada uma das varetas seja divisível por k, ou diga que isso é impossível.
O Risotto Nero já resolveu esse problema e está esperando você conferir suas respostas.
Entrada:
A primeira linha contém um único inteiro n (1 ≤ n ≤ 10
5) — quantidade de palitos.
A segunda linha contém n inteiros a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — o número inicial de anéis em cada uma das varetas.
Saída:
Se a solução necessária não existir, imprima −1.
Caso contrário, imprima x — o número mínimo de ações para levar o quebra-cabeça ao estado desejado.
Exemplos:
| Entrada |
Saída |
3
1 0 1
| 2 |
1
1 |
-1 |
Explicação:
No primeiro exemplo, você pode primeiro mover o anel do terceiro bastão para o segundo e depois do segundo para o primeiro. Depois disso, o número de anéis em cada uma das varas será dividido por 2.