Modified Nim Game with Initial Pile Removals

In the traditional Nim game, there are several piles of matches. In each turn a player may remove any positive number of matches from exactly one pile. The player who removes the last match wins the game.

This problem introduces a twist. In the first round:

• The first player (you) chooses a subset of piles and removes all the matches in each chosen pile. You are allowed to remove no piles (i.e. choose the empty subset), but you cannot remove all piles.
• Then the second player, from the remaining piles, also removes a subset of entire piles. (He may remove none but is not allowed to remove all of the remaining piles.)

After these moves, the game proceeds as standard Nim with the remaining piles and the first player's turn. Under perfect play, in standard Nim a position is winning for the player whose turn it is if and only if the xor (⊕) of all pile sizes is nonzero.

Your goal is to choose your first move (i.e. select a subset S of piles to remove, with S not equal to the full set) such that no matter how the opponent subsequently removes some (but not all) of the remaining piles, the resulting position (with pile set B = A\S minus the opponent's removal) is winning for you (that is, its xor is nonzero).

Let A be the multiset of all pile sizes and let X = \(\bigoplus_{a\in A} a\). If you remove a subset S (with \(Y=\bigoplus_{s\in S}s\)), then the remaining set is B = A\S and its xor is \(X\oplus Y\). In the opponent’s move, he may remove any proper subset T of B. After his move, the piles remaining are \(B\setminus T\), and their xor will be \((X\oplus Y)\oplus Z\) where \(Z\) is the xor of the elements in T. Notice that if the opponent can choose a T (with T not equal to B) such that \(Z = X\oplus Y\), then the nim‐sum becomes 0 and the normal play ensures that you lose.

Thus, a first move S is winning if and only if:

• \(X\oplus Y \neq 0\), and
• There is no proper subset T of B = A\S (i.e. T ⊊ B) with \(\bigoplus_{t\in T} t = X\oplus Y\).

Observation: It turns out that the second condition is equivalent to requiring that the set B is linearly independent when considered as vectors in \(\mathbb{F}_2\) (i.e. via the binary representation of the numbers). Thus, your move S is winning if:

• \(X\oplus Y \neq 0\), and
• The remaining piles B = A\S form a linearly independent set (over GF(2)).

If there is a winning move for you, you must choose one that minimizes the total number of matches removed in the first round (i.e. the sum of the sizes of piles in S). If no winning move exists, output -1.

Input Format: The first line contains an integer n (the number of piles). The second line contains n space‐separated positive integers, where the i-th integer represents the number of matches in the i-th pile.

Output Format: Output a single integer representing the minimal total number of matches removed in your first move that guarantees a win, or -1 if no winning first move exists.

Note: In the first move, you are allowed to remove no piles (i.e. S can be empty) but you are not allowed to remove all piles.

inputFormat

The input begins with a line containing a single integer n (the number of piles).

The next line contains n space-separated integers, each representing the number of matches in a pile.

outputFormat

Output a single integer: the minimal total number of matches you must remove on your first move to guarantee a win, or -1 if no winning strategy exists.

sample

2
1 2

0