求卡常，呜呜呜呜呜呜

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int N = 5e4+10;

#define int register long long

ll n,Q,ct;
ll a[N],ra[N],pf[N],rpf[N];
ll lb[20],rb[20],bl[N];
ll st[16][16][N];
ll mx[N],tp[N];

inline void chk(ll &x,ll y){
    x=x<y?y:x;
}

inline void sol(int l,int r){
    ll q[N],h,t;
    h=1,t=0;
    for (int i=l; i<=n; i++){
        while (h<=t && q[h]<i-r) h++;
        while (h<=t && pf[q[t]]>=pf[i-l]) t--;
        q[++t]=i-l;
        chk(tp[i-l+1],pf[i]-pf[q[h]]);
    }
    h=1,t=0;
    for (int i=l; i<=n; i++){
        while (h<=t && q[h]<i-r) h++;
        while (h<=t && rpf[q[t]]>=rpf[i-l]) t--;
        q[++t]=i-l;
        chk(tp[n-i+1],rpf[i]-rpf[q[h]]);
    }
    h=1,t=0;
    for (int i=1; i<=n; i++){
        while (h<=t && q[h]+l-1<i) h++;
        while (h<=t && tp[q[t]]<=tp[i]) t--;
        q[++t]=i;
        chk(mx[i],tp[q[h]]);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

  //  freopen("query.in","r",stdin);
  //  freopen("query.out","w",stdout);
    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>a[i];
        ra[i]=a[i];
    }
    reverse(ra+1,ra+1+n);
    for (int i=1; i<=n; i++){
        pf[i]=pf[i-1]+a[i];
        rpf[i]=rpf[i-1]+ra[i];
    }
    for (int i=1; i; i++){
        lb[i]=rb[i-1]+1;
        rb[i]=min(n,lb[i]+lb[i]);
        for (int j=lb[i]; j<=rb[i]; j++){
            bl[j]=i;
        }
        ct=i;
        if (rb[i]==n){
            break;
        }
    }
    for (int i=1; i<=ct; i++){
        for (int j=1; j<=n; j++) tp[j]=mx[j]=-1e18;
        sol(lb[i],rb[i]);
        for (int j=1; j<=n; j++){
            st[i][i][j]=mx[j];
        }
    }
    for (int i=ct; i; i--){
        for (int j=i+1; j<=ct; j++){
            for (int k=1; k<=n; k++){
                st[i][j][k]=max(st[i][i][k],st[i+1][j][k]);
            }
        }
    }
    cin>>Q;
    while (Q--){
        int l,r;
        cin>>l>>r;
        for (int j=1; j<=n; j++) tp[j]=mx[j]=-1e18;
        if (l*2>=r){
            sol(l,r);
            ull ans=0;
            for (int i=1; i<=n; i++){
                ans^=(ull)i*mx[i];
            }
            cout<<ans<<"\n";
            continue;
        }
        sol(l,rb[bl[l]]);
        for (int j=1; j<=n; j++) tp[j]=-1e18;
        sol(lb[bl[r]],r);
        if (bl[l]+1<=bl[r]-1){
            for (int i=1; i<=n; i++){
                chk(mx[i],st[bl[l]+1][bl[r]-1][i]);
            }
        }
        ull ans=0;
        for (int i=1; i<=n; i++){
            ans^=(ull)i*mx[i];
        }
        cout<<ans<<"\n";
    }
    return 0;
}