Problem
Récemment, Risotto Nero a découvert les tours de Hanoï et il a vraiment aimé ce puzzle. Cependant, il en a eu marre de jouer sur papier, alors il a décidé de les reproduire dans la vraie vie.
Cependant, Risotto Nero n'avait que des anneaux du même rayon, il a donc proposé un puzzle différent.
Il y a n bâtons. Initialement, chacun d'eux a soit exactement un anneau, soit aucun. En même temps, au moins un anneau est présent sur l'un des bâtons.
En une seule action, vous pouvez transférer l'anneau sur une baguette adjacente.
Il est nécessaire que le nombre minimum d'actions aboutisse à une situation telle qu'un entier k > 1 tel que le nombre d'anneaux sur chacun des bâtons soit divisible par k, ou dire que c'est impossible.
Risotto Nero a déjà résolu ce problème et attend que vous vérifiiez vos réponses.
Saisie :
La première ligne contient un seul entier n (1 ≤ n ≤ 10
5) — nombre de bâtons.
La deuxième ligne contient n entiers a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — le nombre initial de sonneries sur chacun des bâtons.
Sortie :
Si la solution requise n'existe pas, écrivez &moins;1.
Sinon, imprimez x — le nombre minimum d'actions pour amener le puzzle à l'état souhaité.
Exemples :
| Entrée |
Sortie |
3
1 0 1
| 2 |
1
1 |
-1 |
Explication :
Dans le premier exemple, vous pouvez d'abord déplacer l'anneau du troisième stick au second, puis du second au premier. Après cela, le nombre d'anneaux sur chacun des bâtons sera divisé par 2.