rt,WA 80pts

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,q,a[20005],b[20005],c[20005],bl[20005],ans[200][20005],sum1[200][20005],sum2[200][20005],
block,pos[20005],cnt[20005],sum[20005],mus[20005],l1,r1,l2,r2,lst;//<->=
inline int s(int l,int r,int x){
	int res=0;
	for(int i=l;i<=min(r,bl[l]*block);i++)
		res=res+(x<=a[i])*2-1;
	if(bl[l]^bl[r])
		for(int i=(bl[r]-1)*block+1;i<=r;i++)
			res=res+(x<=a[i])*2-1;
	for(int i=bl[l]+1;i<bl[r];i++)
		res+=ans[i][x];
	return res;
}
inline int calc1(int l,int r,int x){
	int res=-1,sm=0;
	if(bl[l]^bl[r]){
		for(int i=l;i<=bl[l]*block;i++)
			sm+=(x<=a[i])*2-1,res=max(res,sm);
		for(int i=bl[l]+1;i<bl[r];i++)
			res=max(res,sm+sum1[i][x]),sm+=ans[i][x];
		for(int i=(bl[r]-1)*block+1;i<=r;i++)
			sm+=(x<=a[i])*2-1,res=max(res,sm);
	}
	else for(int i=l;i<=r;i++)
		sm+=(x<=a[i])*2-1,res=max(res,sm);
	return res;
}
inline int calc2(int l,int r,int x){
	int res=-1,sm=0;
	if(bl[l]^bl[r]){
		for(int i=r;i>(bl[r]-1)*block;i--)
			sm+=(x<=a[i])*2-1,res=max(res,sm);
		for(int i=bl[r]-1;i>bl[l];i--)
			res=max(res,sm+sum2[i][x]),sm+=ans[i][x];
		for(int i=bl[l]*block;i>=l;i--)
			sm+=(x<=a[i])*2-1,res=max(res,sm);
	}
	else for(int i=r;i>=l;i--)
		sm+=(x<=a[i])*2-1,res=max(res,sm);
	return res;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	memset(sum1,-1,sizeof(sum1));
	memset(sum2,-1,sizeof(sum2));
	cin>>n,block=sqrt(n);
	for(int i=1;i<=n;i++)
		cin>>a[i],b[i]=a[i],bl[i]=(i-1)/block+1;
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		c[i]=a[i]=lower_bound(b+1,b+n+1,a[i])-b;
		int t=c[i];
		c[i]+=cnt[t];
		cnt[t]++;
		pos[c[i]]=i;
	}
//	for(int i=1;i<=n;i++) cout<<pos[i]<<endl;
	for(int i=1;i<=bl[n];i++){
		sort(c+(i-1)*block+1,c+min(i*block,n)+1);
		sum[(i-1)*block+1]=mus[min(i*block,n)]=-1;
		for(int j=(i-1)*block+2;j<=min(i*block,n);j++)
			sum[j]=sum[j-1]-1;
		for(int j=min(i*block,n)-1;j>(i-1)*block;j--)
			mus[j]=mus[j+1]-1;
	}
	for(int i=1;i<=bl[n];i++){
		for(int j=1,k=(i-1)*block;j<=n;j++){
			while(k<min(i*block,n)&&j>c[k+1]) k++;
			ans[i][j]=(k-(i-1)*block)*-1+(min(n,i*block)-k);
		}
	}
	for(int i=n;i;i--){
		for(int j=1;j<=bl[n];j++)
			sum1[j][i]=sum1[j][i+1],sum2[j][i]=sum2[j][i+1];
		int bi=bl[pos[i]];
		for(int j=(bi-1)*block+1;j<=min(bi*block,n);j++){
			if(j>=pos[i])
				sum[j]+=2,sum1[bi][i]=max(sum1[bi][i],sum[j]);
			if(j<=pos[i])
				mus[j]+=2,sum2[bi][i]=max(sum2[bi][i],mus[j]); 
		}
	}
//	for(int i=1;i<=n;i++)
//		cout<<c[i]<<endl;
//	for(int i=1;i<=bl[n];i++)
//		for(int j=1;j<=n;j++)
//			cout<<i<<' '<<b[j]<<' '<<ans[i][j]<<' '<<sum1[i][j]<<' '<<sum2[i][j]<<'\n';
//	cout<<calc2(1,5,5)<<endl;
	cin>>q;
	while(q--){
		cin>>l1>>r1>>l2>>r2;
		l1=(l1+lst)%n+1,l2=(l2+lst)%n+1,r1=(r1+lst)%n+1,r2=(r2+lst)%n+1;
		if(l1>r1) swap(l1,r1);
		if(r1>l2) swap(l2,r1);
		if(l2>r2) swap(l2,r2);
		if(l1>r1) swap(l1,r1);
		if(r1>l2) swap(l2,r1);
		if(l1>r1) swap(l1,r1);
//		cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<endl;
		int lt=1,rt=n+1;
		while(lt<rt-1){
			int mid=lt+rt>>1;
			if(calc2(l1,r1,mid)+s(r1+1,l2-1,mid)+calc1(l2,r2,mid)>=0)
				lt=mid;
			else rt=mid;
		}
		cout<<b[lt]<<'\n',lst=b[lt];
	} 
	return 0;
}