Problem
اخیراً Risotto Nero متوجه برج های هانوی شده و از این پازل بسیار خوشش آمده است. با این حال، او از بازی روی کاغذ خسته شد، بنابراین تصمیم گرفت آنها را در زندگی واقعی بازتولید کند.
با این حال، Risotto Nero فقط حلقه هایی با شعاع یکسان داشت، بنابراین او پازل متفاوتی را ارائه کرد.
n چوب وجود دارد. در ابتدا، هر یک از آنها یا دقیقا یک حلقه دارند، یا هیچ یک. در همان زمان، حداقل یک حلقه در هر یک از چوب ها وجود دارد.
با یک عمل، می توانید حلقه را به یک گرز مجاور منتقل کنید.
برای دستیابی به چنین وضعیتی برای حداقل تعداد اقدامات لازم است که مقداری عدد صحیح k > 1 به طوری که تعداد حلقه های هر یک از چوب ها بر k قابل تقسیم باشد یا بگوییم این غیر ممکن است.
Risotto Nero قبلاً این مشکل را حل کرده است و منتظر است تا پاسخ های خود را بررسی کنید.
ورودی:
خط اول شامل یک عدد صحیح n (1 ≤ n ≤ 10
5) — تعداد چوب.
خط دوم شامل n عدد صحیح a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — تعداد اولیه حلقه های هر یک از چوب ها.
خروجی:
اگر راه حل مورد نیاز وجود نداشت، −1.
را چاپ کنید
در غیر این صورت x — حداقل تعداد اقدامات برای رساندن پازل به حالت دلخواه.
مثال:
<بدن>
| ورودی |
خروجی |
3
1 0 1
| 2 |
1
1 |
-1 |
توضیح:
در مثال اول می توانید ابتدا حلقه را از چوب سوم به دومی و سپس از دومی به اولی منتقل کنید. پس از آن تعداد حلقه های هر یک از چوب ها بر 2 تقسیم می شود.