XOR Island

Time limit3sMemory limit1024 MB

Summary

Given n hat values, find the day on which the first islander can deduce that their hat belongs to an XOR triple (a XOR b = c).

Level: Hard8 of 10
Topics: Bit manipulation, Hash map, Simulation
Solved: No attempts yet

Problem

On an island populated entirely by perfect logicians, each islander wears a hat that displays a positive integer. Each islander can see all other islanders' hats but cannot see their own. An islander has no information about the number on their own hat, other than that it is a positive integer.

One day, a mysterious message appears in the sky: "There exist three distinct islanders such that the XOR of the integers on two of their hats is the integer on the hat of the third." After this message appears, the islanders hold meetings on several days in a row, one meeting per day. At each meeting, any islander who knows for sure that they are part of some triple satisfying the message raises their hand.

Assume that no islander lies or makes mistakes, and each raises their hand as soon as it is possible for them to know that they are part of a triple. How many days will it take for at least one islander to raise their hand at a meeting?

Input

The first line contains a single integer $n$ ( $3 \le n \le 25$ ), the number of islanders.

Each of the next $n$ lines contains a single integer $a$ ( $1 \le a < 2^{25}$ ), the positive integer on an islander's hat.

The input is guaranteed to make the message true: there is at least one triple among the hat integers where one integer equals the XOR of the other two.

Output

Output a single integer, the number of daily meetings it takes for some islander to figure out that their hat is part of some XOR triple. It can be proven that at least one person eventually raises their hand.

Examples2

Example 1
Input
```
3
1
2
3
```
Expected output
```
1
```
Example 2
Input
```
11
9
1
14
2
11
7
6
7
6
5
3
```
Expected output
```
3
```