问题 B: Superbull 超级公牛

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:47 通过:27

题目描述

贝茜和她的朋友们在年度超级公牛冠军赛中打蹄球,而农夫约翰则负责使比赛尽可能地令人兴奋。 

共有 N 支队伍参加比赛,每个队伍都有一个唯一的整数 ID,范围在 1∼230−1,用以和其他队伍区分开。

超级公牛冠军赛采用淘汰制----每场比赛选取两支队伍参赛,赛后其中一支球队要被淘汰,被淘汰的队伍将无法参加接下来的任何比赛。

当只剩下一支队伍时,比赛就结束了。

约翰注意到比赛中的得分十分不寻常。

在任何一场比赛中,两个队的总得分总是等于两个队 ID 的按位异或(XOR)的结果。

例如,队伍 12 和队伍 20 一起比赛,那么这场比赛双方将共得 24 分,因为 01100 XOR 10100 = 11000。

约翰认为,比赛中得分越高,比赛就越令人兴奋。

因此,他希望合理安排一系列比赛,使得超级公牛冠军赛的所有比赛的总得分最大。

请帮助约翰组织比赛。 

输入格式

第一行包含整数 N。  

接下来 N 行包含每支队伍的 ID。 

输出格式

输出超级公牛冠军赛的所有比赛的最大总得分。 


数据范围

1≤N≤2000 

输入样例:

4
3
6
9
10

输出样例:

37

样例解释

一种最佳安排比赛方式如下: 

  1. 安排队伍 3 和 9 比赛,并淘汰队伍 3。
  2. 安排队伍 6 和 9 比赛,并淘汰队伍 9。
  3. 安排队伍 6 和 10 比赛,决出冠军,比赛全部结束

总得分为 (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37。 

输入样例 复制

4
3
6
9
10

输出样例 复制

37

数据范围与提示