Problem Description

An ecological conservation project is assessing the connectivity of an ecological corridor. The project hopes to improve the cooperative interaction between different regions by optimizing the layout of local monitoring sites.

The corridor consists of $n$ monitoring sites arranged in a line. The $i$-th site is assigned a genetic diversity code $a_i$ based on its vegetation coverage and water source distribution.

To evaluate the construction quality of the corridor, the expert group defines an indicator called “interaction intensity”. This intensity is given by the sum of the bitwise XOR of codes of all adjacent sites:

$$(a_1 \oplus a_2) + (a_2 \oplus a_3) + \dots + (a_{n-1} \oplus a_n)$$

Research shows that the larger the code difference (XOR value) between adjacent sites is, the more active gene exchange becomes during species migration.

In the later optimization stage of the project, engineers may choose two non-overlapping consecutive segments of length $3$ on the whole line (only once), and rearrange the three sites within each segment (i.e., change their internal order). The order after rearrangement may be the same as the original.

If the starting indices of the two chosen segments are $i$ and $j$, then they must satisfy:

• $1 \le i, j \le n - 2$;
• $|i - j| \ge 3$.

Now, please help the engineers design the best local adjustment plan, and compute the maximum possible cooperative interaction intensity of the corridor after optimization.

Input Format

The first line contains a positive integer $n$, representing the number of monitoring sites.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, representing the initial genetic diversity codes of the monitoring sites.

Output Format

Output one integer, representing the maximum cooperative interaction intensity after optimization.

7
1 2 3 4 5 6 7

26

Hint

[Sample Explanation]

You can choose two length $3$ segments with starting positions $2$ and $5$.

Rearrange the numbers from position $2$ to position $4$ from $2 \ \ 3 \ \ 4$ to $2 \ \ 4 \ \ 3$, and keep the numbers from position $5$ to position $7$ as $5 \ \ 6 \ \ 7$. The sequence becomes:

$1 \ \ 2 \ \ 4 \ \ 3 \ \ 5 \ \ 6 \ \ 7$

The interaction intensity is:

$$(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 7) = 26.$$

It can be proven that no larger interaction intensity can be obtained, so the answer is $26$.

[Constraints and Notes on Testdata]

For $40\%$ of the testdata, $6 \le n \le 500$.

For all testdata, $6 \le n \le 2 \times 10^5$, $0 \le a_i \le 10^9$.

Translated by ChatGPT 5