/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
チーターと不正者がニムをすることになりました。 このゲームでは、N 個の石の山を使います。 最初に i 番目の山には a_i 個の石があります。 チーターが先手で、交互にターンを取ります。 それぞれのターンでは、プレイヤーは一つの山を選び、その山から一個以上の石を取り除きます。 ターンが回ってきたときに操作ができなくなったプレイヤーの負けです。
しかし、ゲームが始まる前に、不正者はチーターがどのような動きをしても必ず勝つことができるように少し不正をすることにしました。 それぞれの山から、不正者は 0 個または 1 個の石を取り除き、ゲームが始まる前に食べます。 不正者が必ず勝てるようにする方法が複数通りある場合は、食べる石の個数を最小にするようにしたいです。
不正者が食べる石の個数を求めてください。
不正をしても不正者が必ず勝つようにできない場合は、-1 を出力してください。
制約
- 1 ≤ N ≤ 10^5
- 2 ≤ a_i ≤ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 : a_N
出力
答えを出力せよ。
入力例 1
3 2 3 4
出力例 1
3
不正者が勝つ唯一の方法は、全ての山から石を取って食べることです。
入力例 2
3 100 100 100
出力例 2
-1
Score : 500 points
Problem Statement
A cheetah and a cheater are going to play the game of Nim. In this game they use N piles of stones. Initially the i-th pile contains a_i stones. The players take turns alternately, and the cheetah plays first. In each turn, the player chooses one of the piles, and takes one or more stones from the pile. The player who can't make a move loses.
However, before the game starts, the cheater wants to cheat a bit to make sure that he can win regardless of the moves by the cheetah. From each pile, the cheater takes zero or one stone and eats it before the game. In case there are multiple ways to guarantee his winning, he wants to minimize the number of stones he eats.
Compute the number of stones the cheater will eat.
In case there is no way for the cheater to win the game even with the cheating, print -1 instead.
Constraints
- 1 ≤ N ≤ 10^5
- 2 ≤ a_i ≤ 10^9
Input
The input is given from Standard Input in the following format:
N a_1 : a_N
Output
Print the answer.
Sample Input 1
3 2 3 4
Sample Output 1
3
The only way for the cheater to win the game is to take stones from all piles and eat them.
Sample Input 2
3 100 100 100
Sample Output 2
-1