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 a_{i} 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 a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 5000), where a_{i} 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.

Difficulty: interview

Starter code:

Solutions:
def dp():
	dparr = [0] * len(sections)
	for i in range(len(sections) - 1, -1, -1):
		_, curend, curcomfort = sections[i]
		nextsection = i + 1
		try:
			while sections[nextsection][0] <= curend:
				nextsection += 1
		except IndexError:
			# Loop til end
			inc = curcomfort
		else:
			inc = curcomfort + dparr[nextsection]
		exc = 0 if i == len(sections) - 1 else dparr[i + 1]
		dparr[i] = max(inc, exc)
	return dparr[0]


n = int(input())
zs = list(map(int, input().split()))
sections = []
seenstartz = set()
first = {z: i for i, z in reversed(list(enumerate(zs)))}
last = {z: i for i, z in enumerate(zs)}
for start, z in enumerate(zs):
	if z in seenstartz:
		continue
	seenstartz.add(z)
	end = last[z]
	comfort = 0
	i = start
	while i <= end:
		if first[zs[i]] < start:
			break
		if i == last[zs[i]]:
			comfort ^= zs[i]
		end = max(end, last[zs[i]])
		i += 1
	else:
		sections.append((start, end, comfort))

ans = dp()
print(ans)


n = int(input())
a = list(map(int, input().split()))

dp = [0]*(n + 1)
f,l = {}, {}
for i in range(len(a)):
    x = a[i]
    if x not in f:
        f[x] = i
    l[x] = i
pr = [a[0]]

for i in range(1, len(a) + 1):
    j = i
    mx = 0
    nums = set()
    curxor = 0
    b = i
    while j > 0:
        x = a[j-1]
        if l[x] > i - 1:
            break
        if x not in nums:
            nums.add(x)
            curxor ^= x
        b = min(b, f[x] + 1)
        if b == j:
            mx = max(mx, dp[j-1] + curxor)
        j -= 1
    dp[i] = max(dp[i-1], mx)
print(dp[len(a)])

people = int(input())
cities = list(map(int, input().split()))
maximum = max(cities)
last, first = [-1 for i in range(maximum + 1)], [float('inf') for i in range(maximum + 1)]
for i in range(people):
    first[cities[i]] = min(i, first[cities[i]])
    last[cities[i]] = max(i, last[cities[i]])
dp = [0 for i in range(people)]
dp[0] = cities[0] if last[cities[0]] == 0 else 0
for i in range(1, people):
    min_first = float('inf')
    max_last = -1
    used = set()
    xor = 0
    for j in range(i, -1, -1):
        min_first = min(min_first, first[cities[j]])
        max_last = max(max_last, last[cities[j]])
        if cities[j] not in used:
            xor ^= cities[j]
        used.add(cities[j])
        if min_first >= j and max_last <= i:
            if j != 0:
                dp[i] = max(dp[i], dp[j - 1] + xor)
            else:
                dp[i] = max(dp[i], xor)
    dp[i] = max(dp[i], dp[i - 1])
print(dp[-1])

import sys

inf = 1<<30

def solve():
    n = int(input())
    a = [0] + [int(i) for i in input().split()]

    maxi = max(a)
    f = [-1] * (maxi + 1)
    for i in range(1, n + 1):
        if f[a[i]] == -1:
            f[a[i]] = i

    l = [-1] * (maxi + 1)
    for i in range(n, 0, -1):
        if l[a[i]] == -1:
            l[a[i]] = i

    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        dp[i] = dp[i - 1]

        if i == l[a[i]]:
            min_l = f[a[i]]
            max_r = i
            used = set()
            v = 0

            for j in range(i, -1, -1):
                min_l = min(min_l, f[a[j]])
                max_r = max(max_r, l[a[j]])

                if a[j] not in used:
                    v ^= a[j]
                    used.add(a[j])

                if max_r > i:
                    break
                if j == min_l:
                    dp[i] = max(dp[i], dp[j - 1] + v)
                    break

    # print(dp)
    ans = dp[n]
    print(ans)

def __starting_point():
    solve()
__starting_point()

#!/usr/bin/pypy3

import cProfile
from sys import stdin,stderr
from heapq import heappush,heappop
from random import randrange

def readInts(): return map(int,stdin.readline().strip().split())
def print_err(*args,**kwargs): print(*args,file=stderr,**kwargs)

def create_heap(ns):
    mins = {}
    maxs = {}
    for i,v in enumerate(ns):
        if v not in mins: mins[v] = i
        maxs[v] = i
    ranges = {}
    rheap = []
    for v,minix in mins.items():
        maxix = maxs[v]
        ranges[v] = (minix,maxix)
        heappush(rheap,(maxix-minix+1,minix))        
    return (ranges,rheap)

def create_heap2(ns):
    mins = {}
    maxs = {}
    for i,v in enumerate(ns):
        if v not in mins: mins[v] = i
        maxs[v] = i
    ranges = {}
    rheap = []
    for v,minix in mins.items():
        maxix = maxs[v]
        ranges[v] = (minix,maxix)
        heappush(rheap,(maxix-minix+1,minix,set([v])))        
    return (ranges,rheap)

def solve(n,ns):
    ranges,pq = create_heap(ns)
    resolved_ranges = {}
    while pq:
        w,lo_ix = heappop(pq)
        #print(len(pq),w,lo_ix)
        if lo_ix in resolved_ranges:
            #print(len(pq))
            continue
        tot_subs = 0
        tot_x = 0
        ix = lo_ix
        fail = False
        xsv = set()
        while ix < lo_ix+w:
            v = ns[ix]
            lo2,hi2 = ranges[v]
            if lo2 < lo_ix or hi2 > lo_ix+w-1:
                lo2 = min(lo2,lo_ix)
                hi2 = max(hi2,lo_ix+w-1)
                heappush(pq, (hi2-lo2+1,lo2) )
                fail = True
                break
            if ix in resolved_ranges:
                rhi_ix,c,x = resolved_ranges[ix]
                tot_x ^= x
                tot_subs += c
                ix = rhi_ix + 1
                continue
            if v not in xsv:
                xsv.add(v)
                tot_x ^= v
            ix += 1
        if not fail:
            resolved_ranges[lo_ix] = (lo_ix+w-1,max(tot_x,tot_subs),tot_x)
    ix = 0
    tot_c = 0
    while ix < n:
        rhi,c,_ = resolved_ranges[ix]
        ix = rhi+1
        tot_c += c
    return tot_c


def solve2(n,ns):
    ranges,pq = create_heap(ns)
    resolved_ranges = {}
    while pq:
        w,lo_ix,xs = heappop(pq)
        print(len(pq),w,lo_ix,xs)
        if lo_ix in resolved_ranges:
            print(len(pq))
            continue
        tot_subs = 0
        tot_x = 0
        for x in xs: tot_x ^= x
        ix = lo_ix
        fail = False
        while ix < lo_ix+w:
            v = ns[ix]
            if v in xs:
                ix += 1
                continue
            if ix in resolved_ranges:
                rhi_ix,c,x = resolved_ranges[ix]
                tot_x ^= x
                tot_subs += c
                ix = rhi_ix + 1
                continue
            lo2,hi2 = ranges[v]
            lo2 = min(lo2,lo_ix)
            hi2 = max(hi2,lo_ix+w-1)
            xs.add(v)
            heappush(pq, (hi2-lo2+1,lo2,xs) )
            fail = True
            break
        if not fail:
            resolved_ranges[lo_ix] = (lo_ix+w-1,max(tot_x,tot_subs),tot_x)
    ix = 0
    tot_c = 0
    while ix < n:
        rhi,c,_ = resolved_ranges[ix]
        ix = rhi+1
        tot_c += c
    return tot_c

def test():
    n = 5000
    ns = []
    for _ in range(n):
        ns.append(randrange(1,n//2))
    print(solve(n,ns))
    
def run():
    n, = readInts()
    ns = list(readInts())
    print(solve(n,ns))
        
run()


n = int(input())
a = [int(i) for i in input().split()]

#a_set = set(a)
prefix = dict()
suffix = dict()
for i in range(n):
    if a[i] not in prefix:
        prefix[a[i]] = i
    suffix[a[i]] = i
dp = [ 0 for i in range(n+1)]
for i in range(n):
    dp[i] = dp[i-1]
    if suffix[a[i]] != i:
        continue
    cur = 0
    min_ind = prefix[a[i]]
    for j in range(i, -1, -1):
        if suffix[a[j]] <= i:
            if suffix[a[j]] == j:
                cur = cur ^ a[j]
            min_ind = min(min_ind, prefix[a[j]])
            if j == min_ind:
                dp[i] = max(dp[i], dp[j-1] + cur)
        else:
            break
print(dp[n-1])

n = int(input())
a = list(map(int, input().split()))
R, L = {}, {}
for i in range(n):
    if a[i] not in L:
        L[a[i]] = i
    R[a[i]] = i

dp = [0] * (n + 1)
for i in range(n):
    dp[i] = dp[i - 1]
    if R[a[i]] != i:
        continue
    s = 0
    l = L[a[i]]
    for j in range(i, -1, -1):
        if R[a[j]] <= i:
            if R[a[j]] == j:
                s ^= a[j]
            l = min(l, L[a[j]])
            if j == l:
                dp[i] = max(dp[i], dp[j - 1] + s)
        else:
            break

print(dp[n - 1])

from collections import Counter, defaultdict

R = lambda: map(int, input().split())
n = int(input())
arr = list(R())
cnts = Counter(arr)
dp = [0] * (n + 1)
for i in range(n):
    acc = defaultdict(int)
    cnt, xor = 0, 0
    dp[i] = dp[i - 1]
    for j in range(i, -1, -1):
        acc[arr[j]] += 1
        if acc[arr[j]] == cnts[arr[j]]:
            cnt += 1
            xor = xor ^ arr[j]
        if len(acc) == cnt:
            dp[i] = max(dp[i], dp[j - 1] + xor)
print(dp[n - 1])

"""
from
http://codeforces.com/contest/811/problem/C
"""
length = int(input())
array = [0] + [int(x) for x in input().split()]
dp = [0]*(length+1)
end = [0]*5001
start = [5001]*5001
vis = [0]*5001

for i in range(1,length+1):
    start[array[i]] = min(start[array[i]],i)
    end[array[i]] = max(end[array[i]],i)

for i in range(1, length + 1):
    dp[i] = dp[i-1]
    chk = [0] * 5001
    ll = i
    cur = 0
    for j in range(i,0,-1):
        ll = min(ll,start[array[j]])
        if end[array[j]] > i:break
        if chk[array[j]] == 0:
            cur = array[j] ^ cur
            chk[array[j]] = 1
        if ll == j:
            dp[i] = max(dp[i],dp[j-1]+cur)
print(dp[length])

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
n=int(input())
a=input()
b=list(map(int,a.strip().split()))
L={}
R={}
vis={}
dp=[]
for i in range(n):
    if L.get(b[i])==None:
        L[b[i]]=i
    R[b[i]]=i
    dp.append(0)
dp.append(0)
for i in range(n):
    vis.clear()
    if i>0:
        dp[i]=dp[i-1]
    ans=0
    Min=i
    j=i
    while j>=0:
        t=b[j]
        if vis.get(t)==None:
            if R[t]>i:
                break
            Min=min(Min,L[t])
            ans^=t
            vis[t]=1
        if j<=Min:
            dp[i]=max(dp[i],dp[j-1]+ans)
        j-=1
print(dp[n-1])