Problem
最近、Risotto Nero はハノイの塔について知り、このパズルがとても気に入りました。しかし、彼は紙の上で遊ぶのに飽きたので、それらを実際に再現することにしました。
しかし、Risotto Nero には同じ半径のリングしかなかったため、別のパズルを考え出しました。
n 本の棒があります。最初は、それぞれのリングが 1 つだけであるか、まったくないかのいずれかです。同時に、いずれかのスティックに少なくとも 1 つのリングが存在します。
ワンアクションでリングを隣のワンドに移すことができます。
いくつかの整数ｋ＞１であるような状況を達成するために、アクションの最小数が必要である。 1 で、各スティックのリングの数が k で割り切れる、またはこれは不可能であると言います。
Risotto Nero はすでにこの問題を解決しており、回答を確認するのを待っています。
入力:
最初の行には、単一の整数 n (1 ≤ n ≤ 10
5) が含まれています —スティックの数。
2 行目には n 個の整数 a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — が含まれます。各スティックのリングの初期数。
出力:
必要な解決策が存在しない場合は、−1.
を印刷します。
それ以外の場合は x を出力します。パズルを目的の状態にするためのアクションの最小数。
例:
<本体>
| 入力 |
出力 |
3
1 0 1
| 2 |
1
1 |
-1 |
説明:
最初の例では、最初にリングを 3 番目のスティックから 2 番目のスティックに移動し、次に 2 番目から 1 番目のスティックに移動できます。その後、各スティックのリングの数は 2 で割ります。