求卡常

#include<bits/stdc++.h>
#define int long long
const int inf=1e16;
using namespace std;

//IO
#ifdef __unix__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
inline int read() {
    int x = 0, f = 1;
    char ch = gc();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = gc();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = gc();
    }
    return x * f;
}
char s[25];
inline void write(unsigned long long x) {
    if (x == 0) { pc('0'); return; }
    int top = 0;
    while(x) {
        s[++top] = (x % 10) + '0';
        x /= 10;
    }
    while(top) {
        pc(s[top--]);
    }
}



int n,q,a[50005];
int mn[50005][17],mx[50005][17],lg[50005];
inline int qL(int l,int r){
    l=max(l,0ll),r=min(r,n-1);
    if(l>r)return inf;
    int v=lg[r-l+1];
    return min(mn[l][v],mn[r-(1<<v)+1][v]);
}
inline int qR(int l,int r){
    l=max(l,1ll),r=min(r,n);
    if(l>r)return -inf;
    int v=lg[r-l+1];
    return max(mx[l][v],mx[r-(1<<v)+1][v]);
}
int b[50005],c[50005],d[50005],l,r,len,H;
int ps1[50005],ps2[50005],ps3[50005];
int hd1,hd2,hd3,tl1,tl2,tl3;
unsigned long long ans;
signed main(){
    // freopen("query.in","r",stdin);
    // freopen("query.out","w",stdout);
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    // cin>>n;
    n=read();
    // for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=n;i++)a[i]=read()+a[i-1];
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=n;i>=0;i--){
        mn[i][0]=mx[i][0]=a[i];
        for(int j=1;j<=16;j++){
            if(i+(1<<(j-1))>n)mn[i][j]=mn[i][j-1],mx[i][j]=mx[i][j-1];
            else mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]),mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    // cin>>q;
    q=read();
    while(q--){
        // cin>>l>>r;
        l=read(),r=read();
        len=r-l;
        ans=0;
        H=len>>1;
        for(int i=1;i<=n;i++){
            b[i]=qR(i+l-1,i+r-1)-a[i-1];
            c[i]=qR(i+l+H,i+r-1)-a[i-1];
            d[i]=a[i]-qL(i-r,i-l-H-1);
        }
        (hd1=1,tl1=0);(hd2=1,tl2=0);(hd3=1,tl3=0);
        for(int i=1;i<=H;i++){
            while(hd3<=tl3&&d[ps3[tl3]]<=d[i])tl3--;
            ps3[++tl3]=i;
        }
        for(int i=1;i<=n;i++){
            while(hd1<=tl1&&b[ps1[tl1]]<=b[i])tl1--;
            ps1[++tl1]=i;
            while(hd1<=tl1&&ps1[hd1]<i-l+1)hd1++;
            
            if(i>=l)while(hd2<=tl2&&c[ps2[tl2]]<=c[i-l+1])tl2--;
            if(i>=l)ps2[++tl2]=i-l+1;
            while(hd2<=tl2&&ps2[hd2]<i-l-H+1)hd2++;

            if(i+H<=n)while(hd3<=tl3&&d[ps3[tl3]]<=d[i+H])tl3--;
            if(i+H<=n)ps3[++tl3]=i+H;
            while(hd3<=tl3&&ps3[hd3]<i)hd3++;

            int res=qR(i,i+H)-qL(i-l-H,i-l);
            if(hd1<=tl1)res=max(res,b[ps1[hd1]]);
            if(hd2<=tl2)res=max(res,c[ps2[hd2]]);
            if(hd3<=tl3)res=max(res,d[ps3[hd3]]);
            ans^=(unsigned long long)i*res;
        }
        // cout<<ans<<'\n';
        write(ans);puts("");
    }
}