配点 : $500$ 点

問題文

チーターと不正者がニムをすることになりました。 このゲームでは、$N$ 個の石の山を使います。 最初に $i$ 番目の山には $a_i$ 個の石があります。 チーターが先手で、交互にターンを取ります。 それぞれのターンでは、プレイヤーは一つの山を選び、その山から一個以上の石を取り除きます。 ターンが回ってきたときに操作ができなくなったプレイヤーの負けです。

しかし、ゲームが始まる前に、不正者はチーターがどのような動きをしても必ず勝つことができるように少し不正をすることにしました。 それぞれの山から、不正者は 0 個または 1 個の石を取り除き、ゲームが始まる前に食べます。 不正者が必ず勝てるようにする方法が複数通りある場合は、食べる石の個数を最小にするようにしたいです。

不正者が食べる石の個数を求めてください。 不正をしても不正者が必ず勝つようにできない場合は、-1 を出力してください。

制約

• $1 \leq N \leq 10^5$
• $2 \leq a_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$

:

$a_N$

出力

答えを出力せよ。

3
2
3
4

3

不正者が勝つ唯一の方法は、全ての山から石を取って食べることです。

3
100
100
100

-1