ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 BA: 难忘的旅旅

内存限制：256 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：19 通过：11
返回比赛提交提交记录

题目描述

CF链接：https://codeforces.com/problemset/problem/811/C

      CC经常乘火车旅行,他对自己曾经去过的地方记忆犹新，并跟我们分享了他的一次旅行：

      CC在最初在火车站等待出发，现在有n个人（包括CC）想要上车。他们已经按照某种顺序排好了队，每个人都知道自己想去的城市城市代码ai。

       列车长从排队等待出发旅客中选择一些不相交的序列（不需要按片段覆盖整个序列），同一段的人将在同一节车厢内。这些序列段段的选择方式是，如果至少有一个人前往城市x，那么所有前往城市x的人都应该乘坐同一节车厢。这意味着它们不能属于不同的段。请注意，所有前往x市的人，要么乘坐同一节车厢前往x市，要么根本不去任何地方。

       从位置l到位置r的路段上的乘客乘坐火车旅行的舒适度等于从位置l至位置r的段上的乘客的所有不同城市代码的XOR。XOR运算也称为“异或”。

       火车旅行的总舒适度等于每个路段的舒适度之和。

      帮助CC了解最大可能的总体舒适度。

Vladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips:
Vladik is at initial train station, and now n people (including Vladik) want to get on the train. They are already lined up in some order, and for each of them the city code ai is known (the code of the city in which they are going to).
Train chief selects some number of disjoint segments of the original sequence of people (covering entire sequence by segments is not necessary). People who are in the same segment will be in the same train carriage. The segments are selected in such way that if at least one person travels to the city x, then all people who are going to city x should be in the same railway carriage. This means that they can’t belong to different segments. Note, that all people who travel to the city x, either go to it and in the same railway carriage, or do not go anywhere at all.
Comfort of a train trip with people on segment from position l to position r is equal to XOR of all distinct codes of cities for people on the segment from position l to position r. XOR operation also known as exclusive OR.
Total comfort of a train trip is equal to sum of comfort for each segment.
Help Vladik to know maximal possible total comfort.
Input
First line contains single integer n (1≤n≤5000)− number of people.
Second line contains n space-separated integers a1,a2,...,an (0≤ai≤5000), where ai denotes code of the city to which i-th person is going.
Output
The output should contain a single integer− maximal possible total comfort.
Examples
Input 
6
4 4 2 5 2 3
Output 
14
Input 
9
5 1 3 1 5 2 4 2 5
Output 
9
Note
In the first test case best partition into segments is: [4,4] [2,5,2] [3], answer is calculated as follows: 4+(2 xor 5)+3=4+7+3=14
In the second test case best partition into segments is: 5 1 [3] 1 5 [2,4,2] 5, answer calculated as follows: 3+(2 xor 4)=3+6=9.

输入格式

第一行包含单个整数n（1≤n≤5000)− 人数。

第二行包含n个空格分隔的整数a1，a2，…，an（0≤ai≤5000），其中ai表示第i个人要去的城市的代码。

 



输出格式

输出应包含单个整数− 最大可能的总体舒适度。

输入

6

4 4 2 5 2 3

输出

14

输入

9

5 1 3 1 5 2 4 2 5

输出

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。





输入样例 复制 

6

4 4 2 5 2 3

输出样例 复制 

14

分类标签