Vladik 经常乘坐火车旅行。他对他的一些旅行记得特别清楚,我想告诉你其中一次旅行:
Vladik 位于初始火车站,现在有 n 个人(包括 Vladik)想要上车。它们已经按某种顺序排列起来,并且每个城市的城市代码 ai 都是已知的(它们要去的城市的代码)。
列车长选择原始人员序列中一些不相交的片段(不需要按片段覆盖整个序列)。同一区段的人将乘坐同一节车厢。路段的选择方式是,如果至少有一个人前往城市 x,则所有前往城市 x 的人都应该乘坐同一节火车车厢。这意味着它们不能属于不同的细分市场。请注意,所有前往城市 x 的人要么乘坐同一辆火车车厢前往该城市,要么根本不去任何地方。
从位置l到位置r的路段上的人员乘坐火车旅行的舒适度等于从位置l到位置r的路段上的人员的所有不同城市代码的异或。 XOR 运算也称为异或。
火车旅行的总舒适度等于各路段舒适度之和。
帮助 Vladik 了解最大可能的总体舒适度。
输入
第一行包含单个整数 n (1 ≤ n ≤ 5000) – 人数。
第二行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 5000),其中 ai 表示第 i 个人要去的城市的代码。
输出
输出应包含一个整数 - 最大可能的总舒适度。
示例
输入 #1
6 4 4 2 5 2 3
输出 #1
14
输入 #2
9 5 1 3 1 5 2 4 2 5
输出 #2
9
注意
在第一个测试用例中,最佳划分为:[4, 4] [2, 5, 2] [3],答案计算如下: 4 + (2 xor 5) + 3 = 4 + 7 + 3 = 14
在第二个测试用例中,最佳划分为: 5 1 [3] 1 5 [2, 4, 2] 5,答案计算如下: 3 + (2 xor 4) = 3 + 6 = 9。