Superbull#11181
Bessie and her friends are playing hoofball in the annual Superbull Championship, and Farmer John is in charge of making the tournament as exciting as possible. A total of teams are competing in the Superbull. Each team is assigned a distinct integer team ID in the range to 2^{30}-1 to distinguish it from the other teams.
The Superbull is an elimination tournament. After each game, Farmer John chooses which of the two teams to eliminate, and the eliminated team can no longer participate in any further games. The tournament ends when only one team remains.
Farmer John notices a very unusual property of the scores in these matches. In every game, the total number of points scored by the two teams is equal to the bitwise exclusive OR (XOR) of their team IDs. For example, if teams and play against each other, the game produces points, since 01100~XOR~10100 = 11000.
Farmer John believes that the more points are scored in a game, the more exciting the game is. Therefore, he wants to choose a sequence of games such that the total number of points scored throughout the Superbull is as large as possible. Please help Farmer John organize the matches.
The first line contains one integer n~(1 \le n \le 2000). The following lines each contain a single team ID.
Print the maximum possible total number of points that can be scored in the Superbull.
One way to achieve a total of points is as follows. FJ first matches teams and and decides that team wins, leaving teams , , and in the tournament. He then matches teams and and lets team win. Teams and are now left in the tournament. Finally, teams and face off, and team wins.
The total number of points scored is
Example 1
The bitwise exclusive OR operation, commonly denoted by the symbol, is a bitwise operation that applies the logical exclusive OR to each corresponding pair of bits in two binary integers. The result in each position is if exactly one of the two bits is , and if both bits are or both are .
For example,
(decimal ) (decimal ) (decimal ).