再求卡常（玄关）

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define FOR(i,a,b) for(int i=(a),E##i=(b);i<=E##i;i++)
#define REV(i,a,b) for(int i=(a),E##i=(b);i>=E##i;i--)
#define CLOSE_TIE ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define psbk push_back
#define endl '\n'
template <typename T>
void _outval(string s,int p,const T &t) {cout<<s.substr(p,s.length()-p)<<'='<<t<<endl; }
template <typename T, typename... Args>
void _outval(string s,int p,const T &t,const Args &...rest){
    string n="";
    while(s[p]!=',') n+=s[p++];
    cout<<n<<'='<<t<<", ";
    _outval(s,p+1,rest...);
}
#define outval(...) _outval(#__VA_ARGS__,0,__VA_ARGS__)
#define outarr(a,be,ed)\
{cout<<(#a)<<": ";\
FOR(iiii,be,ed)cout<<'['<<iiii<<"]="<<a[iiii]<<(iiii<ed?", ":"\n");}
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
template<typename Tp> inline void read(Tp &x) {x=0; register bool z=true; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=(x<<1)+(x<<3)+(a^48); x=(z?x:~x+1);}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y) {read(x),read(y...);}
template<typename Tp> inline void write(Tp x) {if(!x) return pc(48),void(); if(x<0) pc('-'),x=~x+1; register int len=0; register char tmp[64]; for(;x;x/=10) tmp[++len]=x%10+48; while(len) pc(tmp[len--]);}
const int N=5e4+5;
const int lgN=20;
const ll INF=1e15;
int n,lgn,Q,L,R,lg[N];
ll a[N],sum[N],ans[N],f[N],g[N],b[lgN][N],q[N];
struct ST{
    ll mx[lgN][N],mn[lgN][N];
    void init(int n,ll a[]){
        FOR(i,0,n) mx[0][i]=mn[0][i]=a[i];
        FOR(i,1,lg[n])
            FOR(j,0,n-(1<<i)+1){
                mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
                mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
            }
    }
    ll queryMax(int l,int r){
        int lgl=lg[r-l+1];
        return max(mx[lgl][l],mx[lgl][r-(1<<lgl)+1]);
    }
    ll queryMin(int l,int r){
        int len=r-l+1,lgl=lg[len];
        return min(mn[lgl][l],mn[lgl][r-(1<<lgl)+1]);
    }
}st;
struct SmallST{
    ll mx[5][lgN];
    void init(int n,int k){
        FOR(i,0,n) mx[0][i]=b[i][k];
        FOR(i,1,lg[n])
            FOR(j,0,n-(1<<i)+1)
                mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
    }
    ll queryMax(int l,int r){
        int lgl=lg[r-l+1];
        return max(mx[lgl][l],mx[lgl][r-(1<<lgl)+1]);
    }
}stSml[N];
inline void solve(int l,int r){
    if(r-l+1<L) return;
    if(l==r){
        if(L==1) ans[l]=max(ans[l],a[l]);
        return;
    }
    int mid=(l+r)>>1,le=min(n,l+L-2),ri=min(n,l+R-2);
    ll now=-INF;
    FOR(i,l,mid){
        if(i+L-1<=n){
            if(le<n) ++le;
            if(ri<n) ++ri;
            int ll=max(le,mid+1),rr=min(ri,r);
            if(ll<=rr) now=max(now,st.queryMax(ll,rr)-sum[i-1]);
        }
        ans[i]=max(ans[i],now);
    }
    now=-INF,le=max(r-R+2,1),ri=max(r-L+2,1);
    REV(i,r,mid+1){
        if(i-L+1>=1){
            if(le>1) --le;
            if(ri>1) --ri;
            int ll=max(le,l)-1,rr=min(ri,mid)-1;
            if(ll<=rr) now=max(now,sum[i]-st.queryMin(ll,rr));
        }
        ans[i]=max(ans[i],now);
    }
    solve(l,mid),solve(mid+1,r);
}
inline void small(int L,int R){
    int ri=R-1;
    FOR(i,1,n){
        if(ri<n) ++ri;
        f[i]=(i+L-1<=n?st.queryMax(i+L-1,ri)-sum[i-1]:-INF);
        g[i]=(i-L+1>0?sum[i]-st.queryMin(max(i-R+1,1)-1,i-L):-INF);
    }
    int hdf=0,tlf=-1,hdg=0,tlg=-1;
    FOR(i,1,n){
        while(hdf<=tlf&&q[hdf]<i-L+1) ++hdf;
        while(hdf<=tlf&&f[q[tlf]]<f[i]) --tlf;
        q[++tlf]=i;
        ans[i]=max(ans[i],f[q[hdf]]);
    }
    REV(i,n,1){
        while(hdg<=tlg&&q[hdg]>i+L-1) ++hdg;
        while(hdg<=tlg&&g[q[tlg]]<g[i]) --tlg;
        q[++tlg]=i;
        ans[i]=max(ans[i],g[q[hdg]]);
    }
}
map<pair<int,int>,ull>mp;
signed main(){
    CLOSE_TIE
    read(n);
    lg[0]=-1;
    FOR(i,1,n){
        lg[i]=lg[i>>1]+1;
        read(a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    lg[n+1]=lg[(n+1)>>1]+1; lgn=lg[n];
    st.init(n+1,sum);
    FOR(i,1,n) b[0][i]=a[i];
    FOR(k,1,lgn){
        L=(1<<k),R=(1<<(k+1))-1;
        FOR(i,1,n) ans[i]=-INF;
        solve(1,n);
        FOR(i,1,n) b[k][i]=ans[i];
    }
    FOR(i,1,n) stSml[i].init(lgn+1,i);
    read(Q);
    while(Q--){
        read(L,R); if(mp.count({L,R})){cout<<mp[{L,R}]<<"\n"; continue;}
        ull ANS=0;
        int lgL=lg[L],lgR=lg[R];
        FOR(i,1,n) ans[i]=(lgL+1<=lgR-1?stSml[i].queryMax(lgL+1,lgR-1):-INF);
        if(lgL==lgR) small(L,R);
        else small(L,(1<<(lgL+1))-1),small((1<<lgR),R);
        FOR(i,1,n) ANS^=(ull)i*ans[i];
        cout<<ANS<<"\n";
    }
    return 0;
}