Problem
Baru-baru ini, Risotto Nero mengetahui tentang menara Hanoi, dan dia sangat menyukai teka-teki ini. Walau bagaimanapun, dia bosan bermain di atas kertas, jadi dia memutuskan untuk menghasilkan semula mereka dalam kehidupan sebenar.
Walau bagaimanapun, Risotto Nero hanya mempunyai cincin dengan jejari yang sama, jadi dia menghasilkan teka-teki yang berbeza.
Terdapat n batang. Pada mulanya, setiap daripada mereka sama ada mempunyai tepat satu cincin, atau tiada. Pada masa yang sama, sekurang-kurangnya satu cincin terdapat pada mana-mana kayu.
Dengan satu tindakan, anda boleh memindahkan cincin ke tongkat bersebelahan.
Bilangan tindakan minimum adalah perlu untuk mencapai keadaan sedemikian sehingga beberapa integer k > 1 supaya bilangan gelang pada setiap kayu boleh dibahagi dengan k, atau katakan bahawa ini adalah mustahil.
Risotto Nero telah pun menyelesaikan masalah ini dan sedang menunggu untuk anda menyemak jawapan anda.
Input:
Baris pertama mengandungi integer tunggal n (1 ≤ n ≤ 10
5) — bilangan batang.
Baris kedua mengandungi n integer a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — bilangan awal gelang pada setiap kayu.
Output:
Jika penyelesaian yang diperlukan tidak wujud, cetak &tolak;1.
Jika tidak cetak x — bilangan minimum tindakan untuk membawa teka-teki ke keadaan yang dikehendaki.
Contoh:
| Input |
Output |
3
1 0 1
| 2 |
1
1 |
-1 |
Penjelasan:
Dalam contoh pertama, anda boleh mengalihkan cincin dari kayu ketiga ke yang kedua, kemudian dari yang kedua ke yang pertama. Selepas itu, bilangan cincin pada setiap kayu akan dibahagikan dengan 2.