Superbull Championship

Bessie and her friends are playing hoofball in the annual Superbull championship! In this problem, there are N teams (with N satisfying \(1 \le N \le 2000\)) and each team has a distinct integer team ID in the range \(1 \ldots 2^{30}-1\). The tournament is an elimination tournament: after every game, one team is eliminated, and the process continues until only one team remains.

The twist is in the scoring. In any game played between two teams with IDs \(a\) and \(b\), the total score for that game is \(a \oplus b\) (the bitwise XOR of the two IDs). For example, if teams with IDs 12 and 20 play, then the score is computed as follows:

[ 12_{(10)} = 01100_{(2)} \quad \text{and} \quad 20_{(10)} = 10100_{(2)} ]

[ 01100 \oplus 10100 = 11000 \quad \text{which is } 24_{(10)}. ]

Farmer John, who runs the tournament, wishes to maximize the total number of points scored over the entire tournament. Since exactly \(N-1\) games will be played (one team gets eliminated per game), the problem reduces to selecting \(N-1\) pairings among the teams (each pairing contributing a score of the bitwise XOR of the two team IDs) such that the sum of these scores is maximized.

This is equivalent to finding a maximum spanning tree in a complete graph of \(N\) vertices where the weight of an edge between two teams with IDs \(a\) and \(b\) is \(a \oplus b\).

inputFormat

The first line contains a single integer \(N\), the number of teams.

The second line contains \(N\) distinct integers representing the team IDs. Each team ID is in the range \(1 \ldots 2^{30}-1\).

Example:

4
3 6 9 10

outputFormat

Output a single integer, the maximum total score that can be obtained following the tournament format.

Example:

37

sample

4
3 6 9 10

37