题目描述

给定一个长度为 $n$ 的数列，从中选出两段不重叠的连续子序列，使得第一段连续子序列的异或和 $+$ 第二段连续子序列的异或和 最大。

换句话说，你需要找到两个区间 $[l_1, r_1]$ 和 $[l_2, r_2]$，且同时满足如下条件：

• $1 \le l_1 \le r_1 \lt l_2 \le r_2 \le n$
• $(a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) + (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2})$ 最大。

其中，$\oplus$ 是异或运算符。

输入格式

第一行，一个整数 $n$，表示数列长度。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出一个整数，表示题目所述能够得到的表达式的最大值。

样例

5
1 2 3 1 2

6

说明/提示

样例解释

满足条件的 $(l_1, r_1, l_2, r_2)$ 有：$(1,2,3,3)$，$(1,2,4,5)$，$(3,3,4,5)$。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 5000$
• 对于 $100\%$ 的数据，$2 \le n \le 5 \times 10^5, 0 \le a_i \le 10^9$