Problem Description

Cheetah and the cheater are going to play Nim. In this game, they use $N$ piles of stones. Initially, the $i$-th pile contains $a_i$ stones. Cheetah goes first, and they take turns. On each turn, a player selects one pile and removes one or more stones from it. The player who cannot make a move when their turn comes loses.

However, before the game starts, the cheater decides to cheat a little to ensure they can always win no matter what moves Cheetah makes. From each pile, the cheater can remove either 0 or 1 stone and eat them before the game begins. If there are multiple ways for the cheater to ensure victory, they want to minimize the number of stones eaten.

Determine the number of stones the cheater needs to eat. If it is impossible for the cheater to ensure victory even with cheating, output -1.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ : $ a_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
2
3
4

Sample Output #1

3

Sample Input #2

3
100
100
100

Sample Output #2

-1

Notes/Hints

Constraints

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

Sample Explanation 1

The only way for the cheater to win is to eat a stone from every pile.

见题面 Input 部分

见题面 Output 部分