XOR MST

Time limit2sMemory limit512 MB

Summary

Given N labeled vertices where the edge between any two has weight equal to the XOR of their labels, find the total cost of the minimum spanning tree.

Level: Hard8 of 10
Topics: Trie, Minimum spanning tree, Divide and conquer, Bit manipulation
Solved: No attempts yet

Problem

There is an undirected graph with $N$ vertices. The $i$ -th vertex is labeled with an integer $A_i$ . The weight of the edge connecting vertex $i$ and vertex $j$ is $A_i \oplus A_j$ .

Find the cost of the minimum spanning tree (MST) of this graph.

Input

The first line gives the number of vertices $N$ . The second line gives $A_1, A_2, \ldots, A_N$ .

Output

Print the cost of the MST on the first line.

Constraints

$1 \le N \le 200{,}000$
$0 \le A_i < 2^{30}$

Examples2

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
8
```
Example 2
Input
```
4
1 2 3 4
```
Expected output
```
8
```