P5514 [MtOI2019] Retribution of the Eternal Night

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 silhouettes, but their mind was confused by cute rabbits. Those who lose their way will eventually disappear into the unquenchable eternal night.

Houraisan Kaguya (Kaguya) has a bunch of numbers. Kaguya has $n$ non-negative integers $a_1,a_2\cdots a_n$. Since Kaguya went to play a Gal Game, she hopes that you, who are wise, can help. - You need to divide these numbers into several groups, such that each of the $n$ numbers is assigned to exactly 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. Please find a grouping plan that minimizes the sum of the weights of all groups, and output this minimum value.

The first line 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 one line with one integer representing the answer.

**Explanation for Sample $1$:** One optimal grouping plan is: - Put the $1$st number and the $3$rd number into one group, whose weight is $1\oplus 5 = 4$. - Put the $2$nd number into one group, whose weight is $2$. The sum of the weights of all groups is $4 + 2 = 6$. It can be proven that there is no grouping plan with a smaller total weight sum. **Explanation for Sample $2$:** One optimal grouping plan is: - Put the $1$st number and the $5$th number into one group, whose weight is $9\oplus 9 = 0$. - Put the $2$nd number and the $4$th number into one group, whose weight is $18\oplus 25 = 11$. - Put the $3$rd number and the $6$th number into one group, whose weight is $36\oplus 32 = 4$. The sum of the weights of all groups is $0 + 11 + 4 = 15$. It can be proven that there is no grouping plan with a smaller total weight sum. ### Subtasks - For $80\%$ of the testdata, $n\leq 15$. - For $100\%$ of the testdata, $n\leq 10^6,a_i \leq 10^9$. ### Source [Lost Home 2019 League](https://www.luogu.org/contest/20135) (MtOI2019) T1 Problem setter: disangan233 Translated by ChatGPT 5