贝茜和她的朋友们在年度超级公牛冠军赛中打蹄球,而农夫约翰则负责使比赛尽可能地令人兴奋。
共有 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
一种最佳安排比赛方式如下:
总得分为 (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37。
4
3
6
9
10
37