Problem
Geçenlerde Risotto Nero, Hanoi'nin kulelerini öğrendi ve bu bulmacayı gerçekten beğendi. Ancak kağıt üzerinde oynamaktan sıkıldı ve bu yüzden onları gerçek hayatta çoğaltmaya karar verdi.
Ancak Risotto Nero'nun yalnızca aynı yarıçapa sahip halkaları vardı, bu yüzden farklı bir yapboz buldu.
n çubuk vardır. Başlangıçta, her birinin tam olarak bir halkası vardır veya hiç yoktur. Aynı zamanda, çubukların herhangi birinde en az bir halka bulunur.
Tek bir hareketle yüzüğü bitişikteki bir çubuğa aktarabilirsiniz.
Böyle bir duruma ulaşmak için minimum eylem sayısı gereklidir; 1 öyle ki çubukların her birindeki halka sayısı k ile bölünebilir veya bunun imkansız olduğunu söyleyin.
Risotto Nero zaten bu sorunu çözdü ve cevaplarınızı kontrol etmenizi bekliyor.
Giriş:
İlk satır, tek bir tam sayı n (1 ≤ n ≤ 10
5) — içerir. çubuk sayısı.
İkinci satır n tamsayı içerir a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — çubukların her birindeki ilk çalma sayısı.
Çıktı:
Gerekli çözüm mevcut değilse −1 yazdırın.
Aksi takdirde x yazdır — bulmacayı istenen duruma getirmek için minimum eylem sayısı.
Örnekler:
| Giriş |
Çıktı |
3
1 0 1
| 2 |
1
1 |
-1 |
Açıklama:
İlk örnekte, yüzüğü önce üçüncü çubuktan ikinciye, ardından ikinciden birinciye taşıyabilirsiniz. Bundan sonra, çubukların her birindeki çalma sayısı 2'ye bölünecektir.