← 返回题目列表

Codeforces · 811/C

C. 弗拉迪克和难忘的旅行

中文机器翻译题面 查看原题

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。