/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) が与えられます。この整数列に対して以下の操作を N-1 回行って長さ 1 の整数列を得ることを考えます。
- n を A の長さとする。はじめに A 内の要素を好きなように並び替える。 その後、 A を長さ n-1 の非負整数列 (A_1 \oplus A_2, A_2 \oplus A_3, \dots, A_{n-1} \oplus A_n) に置き換える
ただしここで、 \oplus はビット単位 \mathrm{XOR} 演算を表します。
N-1 回の操作後に得られる長さ 1 の整数列が含む項の値を X としたとき、X として考えられる値の最大値を求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 2 \leq N \leq 100
- 0 \leq A_i < 2^{60}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 1 2 3 4
出力例 1
7
以下のような 3 回の操作により A を A=(7) とできます。
- 1 回目の操作にて、 A=(1,2,3,4) を (3,1,4,2) と並び替える。 A は (3 \oplus 1, 1 \oplus 4, 4 \oplus 2) = (2,5,6) に置き換わる。
- 2 回目の操作にて、 A=(2,5,6) を (2,6,5) と並び替える。 A は (2 \oplus 6, 6 \oplus 5) = (4,3) に置き換わる。
- 3 回目の操作にて、 A=(4,3) を (4,3) と並び替える。 A は (4 \oplus 3) = (7) に置き換わる。
入力例 2
13 451745518671773958 43800508384422957 153019271028231120 577708532586013562 133532134450358663 619750463276496276 615201966367277237 943395749975730789 813856754125382728 705285621476908966 912241698686715427 951219919930656543 124032597374298654
出力例 2
1152905479775702586
Score: 800 points
Problem Statement
You are given a sequence of N non-negative integers A=(A_1,A_2,\dots,A_N). Consider performing the following operation N-1 times on this sequence to obtain a sequence of length 1:
- Let n be the length of A. First, rearrange the elements in A in any order you like. Then, replace A with a sequence of n-1 non-negative integers (A_1 \oplus A_2, A_2 \oplus A_3, \dots, A_{n-1} \oplus A_n).
Here, \oplus represents the bitwise \mathrm{XOR} operation.
Let X be the value of the term contained in the sequence of length 1 obtained after N-1 operations. Find the maximum possible value of X.
What is the bitwise \mathrm{XOR} operation?
The bitwise \mathrm{XOR} of two non-negative integers A and B, denoted as A \oplus B, is defined as follows:
- In the binary representation of A \oplus B, the digit at the 2^k (k \geq 0) position is 1 if the digit at the 2^k position is 1 in A or B but not both, and 0 otherwise.
In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 2 \leq N \leq 100
- 0 \leq A_i < 2^{60}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 1 2 3 4
Sample Output 1
7
The sequence A can be transformed into A=(7) by the following three operations:
- In the first operation, rearrange A=(1,2,3,4) to (3,1,4,2). A is replaced with (3 \oplus 1, 1 \oplus 4, 4 \oplus 2) = (2,5,6).
- In the second operation, rearrange A=(2,5,6) to (2,6,5). A is replaced with (2 \oplus 6, 6 \oplus 5) = (4,3).
- In the third operation, rearrange A=(4,3) to (4,3). A is replaced with (4 \oplus 3) = (7).
Sample Input 2
13 451745518671773958 43800508384422957 153019271028231120 577708532586013562 133532134450358663 619750463276496276 615201966367277237 943395749975730789 813856754125382728 705285621476908966 912241698686715427 951219919930656543 124032597374298654
Sample Output 2
1152905479775702586