Codechef REBXOR

Read problems statements in Mandarin and Russian. Translations in Vietnamese to be uploaded soon.

Nikitosh the painter has a 1-indexed array A of N elements. He wants to find the maximum value of expression

(A[l₁] ⊕ A[l₁ + 1] ⊕ ... ⊕ A[r₁]) + (A[l₂] ⊕ A[l₂ + 1] ⊕ ... ⊕ A[r₂]) where 1 ≤ l₁ ≤ r₁ < l₂ ≤ r₂ ≤ N.

Here, x ⊕ y means the bitwise XOR of x and y.

Because Nikitosh is a painter and not a mathematician, you need to help him in this task.

Input

The first line contains one integer N, denoting the number of elements in the array.

The second line contains N space-separated integers, denoting A₁, A₂, ... , A_N.

Output

Output a single integer denoting the maximum possible value of the given expression.

Constraints

2 ≤ N ≤ 4*10⁵
0 ≤ A_i ≤ 10⁹

Subtasks

Subtask 1 (40 points) : 2 ≤ N ≤ 10⁴
Subtask 2 (60 points) : Original constraints

Example

Input:

5

1 2 3 1 2

Output:

6

Explanation

Choose (l₁, r₁, l₂, r₂) = (1, 2, 3, 3) or (1, 2, 4, 5) or (3, 3, 4, 5).

很久之前做的一道Trie树搞异或的题啦。。。。

大致就是求一下前缀和后缀异或最大值然后更新答案就好了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#define ll int

#define maxn 400005

using namespace std;

long long ans=;

ll ci[];

struct Trie{

    ll ch[maxn*][];

    ll tot,rot;

    void ins(ll x){

        ll now=rot;

        for(int i=;i>=;i--){

            ll c=(ci[i]&x)?:;

            if(!ch[now][c]) ch[now][c]=++tot;

            now=ch[now][c];

        }

    }

    ll find_max(ll x){

        ll now=rot,alr=;

        for(int i=;i>=;i--){

            ll c=(ci[i]&x)?:;

            if(ch[now][c^]) alr+=ci[i],now=ch[now][c^];

            else now=ch[now][c];

        }

        return alr;

    }

}tr;

ll a[maxn],w[maxn],n;

ll lef[maxn],rig[maxn];

inline void init(){

    ci[]=;

    for(int i=;i<=;i++) ci[i]=ci[i-]<<;

    tr.rot=tr.tot=;

}

int main(){

    init();

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",a+i),w[i]=a[i]^w[i-];

    tr.ins();

    for(int i=;i<=n;i++){

        lef[i]=max(lef[i-],tr.find_max(w[i]));

        tr.ins(w[i]);

    }

    memset(tr.ch,,sizeof(tr.ch));

    init();

    for(int i=n;i;i--){

        rig[i]=max(rig[i+],tr.find_max(w[i]));

        tr.ins(w[i]);

    }

    for(int i=;i<=n;i++) ans=max(ans,(long long)(lef[i]+rig[i]));

    printf("%lld\n",ans);

    return ;

}

巴特西