You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明最近在学习异或运算的性质，在做题时遇到了一个需要高效计算异或和最大值的问题。题目要求对于给定的整数序列，找出某个位置 $k$ ，使得该位置元素与序列中所有元素的异或和最大。小明希望你能帮他解决这个问题，以加深对异或运算的理解。 形式化的讲：

给你一个包含 $n$ 个整数的序列 $a_1,a_2,\ldots,a_n$。

在所有 $1 \leq k \leq n$ 中，输出 $(a_k \oplus a_1) + (a_k \oplus a_2) + \ldots + (a_k \oplus a_n)$ 的最大值。注意 $\oplus$ 表示按位异或运算

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——数组的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_i \lt 2^{30}$）。

输出格式

对于每个测试用例，在新的一行输出最大值。

输入输出样例 #1

输入 #1

3
18 18 18

输出 #1

0

输入输出样例 #2

输入 #2

5
1 2 4 8 16

输出 #2

79

说明/提示

在第一个测试用例中，我们能得到的最大值是 $(18 \oplus 18) + (18 \oplus 18) + (18 \oplus 18) = 0$。

在第二个测试用例中，我们选择 $k=5$ 得到 $(16 \oplus 1) + (16 \oplus 2) + (16 \oplus 4) + (16 \oplus 8) + (16 \oplus 16) = 79$。

限制与约定

对于 $40\%$ 的数据，$1 \le n \le 100$ , $0 \le a_i \lt 2^{15}$ 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$ , $0 \le a_i \lt 2^{30}$

• 时间限制: $1 s$
• 空间限制: $256 MB$