Neru's Lost Connection#12447
Neru was watching videos online when her internet connection suddenly disappeared. Now she is angry and wants to reconfigure the connection as chaotically as possible.
The connection consists of consecutive signal cells. The power of the -th cell is equal to p_k.
The instability of the connection depends on neighboring cells. More formally, the value of the connection is defined as
(p_1 \oplus p_2) + (p_2 \oplus p_3) + \ldots + (p_{n-1} \oplus p_n).
To repair the connection, Neru must choose exactly two starting positions and (1 \le i, j \le n-3). For each chosen position, she may rearrange the four consecutive cells starting from this position in any order.
In other words, Neru may independently rearrange the elements of the segments p[i..i+3] and p[j..j+3].
The two chosen segments must not intersect, so |i-j| > 3.
Determine the maximum possible value of the connection after choosing two valid segments and rearranging their elements optimally.
The first line contains one integer (8 \le n \le 2 \cdot 10^5) — the number of signal cells.
The second line contains integers p_1, p_2, \ldots, p_n (0 \le p_i < 2^{30}) — the powers of the signal cells.
Output a single integer — the maximum possible value of the connection after choosing two valid segments and rearranging their elements optimally.
Example 1
Example 2
In the first example, Neru can choose the segments and .
After rearranging them, the array can become [1, 2, 4, 3, 5, 6, 8, 7].
The value of the connection is
(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.
In the second example, one optimal result is [5, 1, 12, 3, 10, 7, 9, 6, 15, 2], and the value of the connection is .
Subtask ( points): n = 8.
Subtask ( points): 8 \le n \le 40.
Subtask ( points): 8 \le n \le 4000.
Subtask ( points): 0 \le p_i \le 1 for all 1 \le i \le n.
Subtask ( points): No additional constraints.