408543: GYM103182 L XorAnd

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$$$.

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$$$.

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

4
3 1 2 1

3

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