Problem
Di recente, Risotto Nero ha scoperto delle torri di Hanoi e questo puzzle gli è piaciuto molto. Tuttavia, si è stancato di giocare sulla carta, quindi ha deciso di riprodurli nella vita reale.
Tuttavia, Risotto Nero aveva solo anelli dello stesso raggio, quindi ha escogitato un puzzle diverso.
Ci sono n bastoncini. Inizialmente, ognuno di loro ha esattamente un anello o nessuno. Allo stesso tempo, almeno un anello è presente su uno qualsiasi dei bastoncini.
Con un'azione, puoi trasferire l'anello su una bacchetta adiacente.
È necessario che il numero minimo di azioni raggiunga una situazione tale che alcuni interi k > 1 in modo tale che il numero di anelli su ciascuno dei bastoncini sia divisibile per k, oppure dire che questo è impossibile.
Risotto Nero ha già risolto questo problema e ti aspetta per verificare le tue risposte.
Inserimento:
La prima riga contiene un singolo numero intero n (1 ≤ n ≤ 10
5) — numero di bastoncini.
La seconda riga contiene n numeri interi a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — il numero iniziale di squilli su ciascuno dei bastoncini.
Uscita:
Se la soluzione richiesta non esiste, stampa −1.
Altrimenti stampa x — il numero minimo di azioni per portare il puzzle allo stato desiderato.
Esempi:
| Input |
Uscita |
3
101
| 2 |
1
1 |
-1 |
Spiegazione:
Nel primo esempio, puoi prima spostare l'anello dal terzo bastoncino al secondo, poi dal secondo al primo. Successivamente, il numero di anelli su ciascuno dei bastoncini sarà diviso per 2.