Max is at the starting station of the train, and now n people (including Max herself) want to get on it. They are already lined up in some order, and each of them knows the area code a
i to which they are going.
The head of the train chooses a certain number of non-intersecting segments of the original sequence of people (the segments do not have to cover the entire sequence). People who are in the same segment will be in the same train car. The segments are chosen so that if at least one person goes to city X, then all people who go to city X will have to be in the same car. This means that they do not have the right to belong to different segments. It should be noted that all people who go to city X either go to it and are in the same car, or do not go anywhere at all.
The comfort of traveling on a train with people on the segment from l to r is equal to the XOR of different city codes for people on the segment from l to r. The XOR operation is also known as bitwise exclusive OR.
The overall comfort of the selected segments is calculated as the sum of the comfort of each individual segment.
Help Max find out the maximum achievable overall comfort.
Input:
The first line contains a natural number n - the number of people.
The second line contains n integers a
i (0 <= a
i <= 5000) - the code of the city the i-th person is going to.
Output:
Print one integer - the maximum overall comfort.
Examples:
| Input |
Output |
6
4 4 2 5 2 3
| 14 |
9
5 1 3 1 5 2 4 2 5
| 9 |