卡常

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef unsigned long long ul;
const int N=1e5+5,V=1e5,R=16;
const int inf=1e10+15;
struct st1{
	vector<int> f[20],g[20];
	void init(int n,int a[]){
		for(int j=0;j<=R;j++){
			f[j].resize(n+5);
			g[j].resize(n+5);
		}
		for(int i=0;i<=n;i++){
			f[0][i]=g[0][i]=a[i];
		}
		for(int j=1;j<=R;j++){
			for(int i=0;(i+(1<<j)-1)<=n;i++){
				f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]);
				g[j][i]=min(g[j-1][i],g[j-1][i+(1<<(j-1))]);
			}
		}
	}
	int que_max(int x,int y){
		if(x>y) return -inf;
		int w=log2(y-x+1);
		return max(f[w][x],f[w][y-(1<<w)+1]);
	}
	int que_min(int x,int y){
		if(x>y) return inf;
		int w=log2(y-x+1);
		return min(g[w][x],g[w][y-(1<<w)+1]);
	}
}t,k[N];
int n,a[N],s[N],q,f[20][N],g[N][20];
int ans[N],res[N],rc[N];
vector<pair<int,int>> rg;
void sol(int x,int l,int r,int res[]){
	if(x==0){
		for(int i=1;i<=n;i++){
			res[i]=a[i];
		}
		return;
	}
	memset(res,-0x3f,sizeof(res[0])*(N-2));
	vector<pair<int,int>> seg;
	int len1=(1<<(x-1));
	for(int i=1;(i+len1-1)<=n;i+=len1){
		int j=i+2*len1-1;
		seg.push_back({i,j});
	}
	int len2=(1<<x);
	for(int i=1;(i+len2-1)<=n;i+=len2){
		int j=i+2*len2-1;
		seg.push_back({i,j});
	}
	for(auto [i,j]:seg){
		int m=(i+j)>>1;
		for(int k=i;k<=j;k++){
			rc[k]=-inf;
		}
		for(int k=i;k<=m;k++){
			if(k!=i) rc[k]=rc[k-1];
			int w=t.que_max(max(m+1,k+l-1),min(j,k+r-1))-s[k-1];
			rc[k]=max(rc[k],w);
		}
		for(int k=j;k>=m+1;k--){
			if(k!=j) rc[k]=rc[k+1];
			int w=s[k]-t.que_min(max(i,k-r+1)-1,min(m,k-l+1)-1);
			rc[k]=max(rc[k],w);	
		}
		for(int k=i;k<=j;k++){
			res[k]=max(res[k],rc[k]);
		}
	}
}
signed main(){
//	freopen("query.in","r",stdin);
// 	freopen("query.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=a[i]+s[i-1];
	}
	for(int i=n+1;i<=V;i++){
		a[i]=-inf;
		s[i]=a[i]+s[i-1];
	}
	t.init(V,s);
	for(int j=0;j<=R;j++){
		if(j==0){
			sol(j,1,1,f[j]);
			rg.push_back({1,1});
		}
		else{
			sol(j,((1<<(j-1))+1),(1<<j),f[j]);
			rg.push_back({((1<<(j-1))+1),(1<<j)});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=R;j++){
			g[i][j]=f[j][i];
		}
		k[i].init(R,g[i]);
	}
	cin>>q;
	while(q--){
		memset(ans,-0x3f,sizeof(ans));
		int l,r;
		cin>>l>>r;
		int mn=inf,mx=0,tg=0;
		for(int k=0;k<(int)rg.size();k++){
			auto [x,y]=rg[k];
			if(l<=x&&x<=y&&y<=r){
				mn=min(mn,k);
				mx=max(mx,k);
				tg=1;
				continue;
			}
			if(max(l,x)<=min(r,y)){
				sol(k,max(l,x),min(r,y),res);
				for(int i=1;i<=n;i++){
					ans[i]=max(ans[i],res[i]);
				}
			}
		}
		if(tg){
			for(int i=1;i<=n;i++){
				int w=k[i].que_max(mn,mx);
				ans[i]=max(ans[i],w);
			}
		}
		ul sc=0;
		for(int i=1;i<=n;i++){
			sc^=(ul)ans[i]*(ul)i;
		}
	 	cout<<sc<<"\n";
	}
}