Largest XOR of two numbers

Problem

Given a list of numbers, find the largest value of a ^ b over all pairs of two different positions. Print that value.

Input: Line 1: n. Line 2: n integers separated by spaces.
Output: One integer: the maximum XOR of two elements at different positions.
Constraints: 2 ≤ n ≤ 2000
0 ≤ value < 2^30

Example

Input

6
3 10 5 25 2 8

Output

5 ^ 25 = 28 is the best pair.

Try the problem first. Open one hint at a time.

Hint 1

Trying every pair costs O(n^2), which is fine for 2000 numbers but not for a million.

Hint 2

Decide the answer bit by bit from the top: keep a guess, and check whether two prefixes can XOR to it.

Write your Python code, run it on the examples and submit it to hidden tests.