Problem Background

In this world, there is a village, a forest, and a bamboo pavilion. There is also a master, a servant, and an enemy.

Someone once wanted to capture their images but was bewitched by the adorable rabbits.

Those lost souls will eventually vanish into the eternal night...

Problem Description

Kaguya from Mount Hou has a set of numbers.

Kaguya has \( n \) non-negative integers \( a_1, a_2, \cdots, a_n \). Since Kaguya is busy playing a Gal Game, she hopes that you, a wise person, can help her.

• You need to divide these numbers into several groups, ensuring that each of the \( n \) numbers is exactly in one group, and each group contains at least one number.

Define the weight of a group as the XOR sum of all numbers in that group. Find a grouping scheme such that the sum of the weights of all groups is minimized, and output the minimum sum of weights.

Input Format

The first line of input contains a positive integer \( n \), representing the number of given non-negative integers.

The next line contains \( n \) non-negative integers \( a_1, a_2, \cdots, a_n \).

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

3
1 2 5

Sample Output #1

6

Sample Input #2

6
9 18 36 25 9 32

Sample Output #2

15

Notes

Sample 1 Explanation:

An optimal grouping scheme is as follows:

• Group the first and third numbers together, the weight of this group is \( 1 \oplus 5 = 4 \);
• Group the second number alone, the weight of this group is \( 2 \).

The sum of the weights of all groups in this scheme is \( 4 + 2 = 6 \). It can be proven that no grouping scheme with a smaller sum of weights exists.

Sample 2 Explanation:

An optimal grouping scheme is as follows:

• Group the first and fifth numbers together, the weight of this group is \( 9 \oplus 9 = 0 \);
• Group the second and fourth numbers together, the weight of this group is \( 18 \oplus 25 = 11 \);
• Group the third and sixth numbers together, the weight of this group is \( 36 \oplus 32 = 4 \).

The sum of the weights of all groups in this scheme is \( 0 + 11 + 4 = 15 \). It can be proven that no grouping scheme with a smaller sum of weights exists.

Subtasks

• For 80% of the data, \( n \leq 15 \).
• For 100% of the data, \( n \leq 10^6, a_i \leq 10^9 \).

Problem Source

MtOI2019 T1

Problem Author: disangan233

见题面 Input 部分

见题面 Output 部分