408543: GYM103182 L XorAnd

Memory Limit:512 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. XorAndtime limit per test0.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

In order to convince his friends that he is the smartest of them all, Tim is trying to compute the biggest XorAnd sum that a subsequence of an array of numbers of length $$$N$$$ can have.

A subsequence of $$$S$$$ is a non-empty sequence $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ with $$$1 \le p_1 < p_2 < \ldots < p_K \le N$$$ for some $$$2 \le K \le N$$$. Two subsequences $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ and $$$S_{q_1}, S_{q_2}, \ldots, S_{q_L}$$$ are different if the sequences $$$p$$$ and $$$q$$$ are different (either $$$K \ne L$$$, or there exists $$$1 \le i \le K$$$ such that $$$p_i \ne q_i$$$).

The XorAnd sum of a subsequence $$$S_{p_1}, S_{p_2}, ..., S_{p_k}$$$ is computed as:

$$$$$$ (S_{p_1} \oplus S_{p_2}) \ \&\ (S_{p_2} \oplus S_{p_3}) \ \&\ \dots \ \&\ (S_{p_{k-1}} \oplus S_{p_k}) $$$$$$

where $$$\oplus$$$ is the bitiwise xor operator and $$$\&$$$ is the bitwise and operator.

Help Tim find the largest XorAnd sum in $$$S$$$.

Input

he first line of the input contains $$$2 \le N \le 10^6$$$, the length of the array.

The second line of the input contains $$$N$$$ integers, $$$S_1, S_2, \ldots, S_N$$$, representing Tim's array.

$$$0 \le S_i \le 10^9$$$ for all $$$1 \le i \le N$$$.

Output

The only line in the output should contain an integer representing the biggest XorAnd sum a subsequence in $$$S$$$ can have.

ExampleInput
4
3 1 2 1
Output
3
Note

The subsequence with the highest XorAnd sum is: [1, 2, 1].

加入题单

上一题 下一题 算法标签: