题目描述

非負整数列 $A\ =\ (A_1,\ \ldots,\ A_N)$ が与えられます。 あなたは次の操作を、何度でも行うことができます（一度も行わなくてもよいです）。

• 非負整数 $x\in\ \{A_1,\ldots,A_N\}$ をひとつ選ぶ。
• すべての $i$ に対して、$A_i$ を $A_i\oplus\ x$ に置き換える（$\oplus$ はビット単位 $\mathrm{XOR}$ 演算を表します）。

操作後の $\sum_{i=1}^N\ A_i$ としてありうる最大値を求めてください。

ビット単位 $\mathrm{XOR}$ 演算とは 非負整数 $A,\ B$ のビット単位 $\mathrm{XOR}$ 、$A\ \oplus\ B$ は、以下のように定義されます。

• $A\ \oplus\ B$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3\ \oplus\ 5\ =\ 6$ となります (二進表記すると: $011\ \oplus\ 101\ =\ 110$)。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $A_1$ $\ldots$ $A_N$

输出格式

操作後の $\sum_{i=1}^N\ A_i$ としてありうる最大値を出力してください。

题目大意

题目描述

给定 $n$ 个非负整数 $a_1,a_2,\dots,a_n$，你可以执行以下操作任意（可以为零）次：

• 选择一个数 $x\in \{a_1,a_2,\dots,a_n\}$。

• 对于所有 $a\leq i\leq n$，将 $a_i$ 修改为 $a_i\oplus x$，其中 $\oplus$ 表示按位异或操作。

请你最大化操作后 $\sum_{i=1}^na_i$ 的值。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一行一个整数，表示操作后 $\sum_{i=1}^na_i$ 的最大值。

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

19

样例 #2

样例输入 #2

5
10 10 10 10 10

样例输出 #2

50

样例 #3

样例输入 #3

5
3 1 4 1 5

样例输出 #3

18

提示

数据范围

• $1\leq n \leq 3\times 10^5$
• $0\leq a_i<2^{30}$

5
1 2 3 4 5

19

5
10 10 10 10 10

50

5
3 1 4 1 5

18

提示

制約

• $1\leq\ N\ \leq\ 3\times\ 10^{5}$
• $0\leq\ A_i\ <\ 2^{30}$

Sample Explanation 1

例えば次のように操作を行うことで、$\sum_{i=1}^N\ A_i$ を $19$ にすることが可能です。 - はじめ、数列 $A$ は次の状態です：$(1,2,3,4,5)$。 - $x\ =\ 1$ として操作を行うと、数列 $A$ は次の状態に変化します：$(0,3,2,5,4)$。 - $x\ =\ 5$ として操作を行うと、数列 $A$ は次の状態に変化します：$(5,6,7,0,1)$。このとき $ \sum_{i=1}^N\ A_i\ =\ 5\ +\ 6\ +\ 7\ +\ 0\ +\ 1\ =\ 19 $ です。

Sample Explanation 2

操作を一度も行わないことで、$\sum_{i=1}^N\ A_i$ を $50$ にすることが可能です。