D: Nose And Lung

問題文

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

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

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

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

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

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

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

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

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

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

-1

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