402494: GYM100792 H Hashing

In this problem you are given a byte array a. What you are going to do is to hash its subsequences. Fortunately you don't have to make a painful choice among infinitely large number of ways of hashing, as we have made this decision for you.

If we consider a subsequence as a strictly increasing sequence s of indices of array a, the hash function of the subsequence is calculated by the formula:

Here, means the bitwise XOR operation. See Note section if you need a clarification.

As you need to store the values in an array after all, you want to know the maximum possible value of the hash function among all subsequences of array a.

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000), denoting the number of bytes in array a. The second line contains n bytes written in hexadecimal numeral system and separated by spaces. Each byte is represented by exactly two hexadecimal digits (0...F).

Output a single integer which is the maximum possible value of the hash function a subsequence of array a can have.

3
03 00 1B

29

3
01 00 02

4

In the first sample one of the best ways is to choose the subsequence 03 00 1B.

In the second sample the only best way is to choose the subsequence 01 02.

Here we are to tell you what a bitwise XOR operation is. If you have two integers x and y, consider their binary representations (possibly with leading zeroes): x_k... x_2x1x0 and y_k... y_2y1y0. Here, x_i is the i-th bit of number x and y_i is the i-th bit of number y. Let be the result of XOR operation of x and y. Then r is defined as r_k... r_2r1r0 where: