D: Nose And Lung

問題文

あなたは謎の敵対的なエイリアンについて研究しています。

エイリアンには鼻の穴が $N$ 個あり、肺が $1$ 個以上あります。 しかし、肺がいくつあるか、および、どの鼻の穴とどの肺が繋がっているかが分かっていません。

あなたはエイリアンに関して、以下の仮説を立てました:

• それぞれの肺は $1$ 個以上の鼻の穴につながっている
• それぞれ鼻の穴は $0$ 個以上の肺につながっている
• 全ての肺に対して酸素が供給されないと死んでしまう。すなわち、ある肺につながっている全ての鼻の穴を塞がれると、エイリアンは死ぬ

政府はあなたの仮説を検証するために、肺と鼻の穴の接続関係がわかっていないエイリアンを $1$ 匹捕獲し、$2^N$ 匹に複製しました。これらのエイリアンで以下のような実験を行いました:

• $i$ 番目 $(i=0, \ldots, 2^N-1)$ のエイリアンに対しては、 $i$ を二進表記した際の $k$ 桁目が $1$ であるような $k$ 番目の鼻の穴を全て塞ぐ ($k = 0, \ldots, N-1$)。
• その結果、エイリアンが生きたままか死んだかを記録する。

あなたはこれらの $2^N$ 個の実験の結果を全て与えられました。 実験の結果が仮説に矛盾していないか判定し、矛盾していない場合には 考えられる肺の最小個数を答えてください。

制約

• 全ての入力は整数である
• $2 \leq N \leq 20$
• $0 \leq a_i \leq 1$
• $a_0 = 0$
• $a_{2^N-1} = 1$

入力

入力は標準入力から以下の形式で与えられます。 ただし、$a_i=1$のとき、$i$番目のエイリアンは死亡し、$a_i=0$のとき、$i$番目のエイリアンは生きていることを表します。

$N$
$a_0$
$:$
$a_{2^N-1}$

出力

実験の結果が仮説に矛盾している場合には $-1$、そうでない場合はエイリアンが持つと考えられる肺の最小個数を答えてください。

入出力例

入力例1

2
0
1
0
1

出力例1

1

考えられる肺のつなげ方としては{{1},{1,2}}や{{1}}があり、最小の個数は1個です。

入力例2

3
0
1
1
1
1
0
0
1

出力例2

-1

2番目の鼻の穴だけを塞いでも3番目の鼻の穴だけを塞いでも死ぬが、両方の穴を塞いだエイリアンは生きているため、仮説に矛盾しています。