只过了样例和 Subtask #1

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+114;
typedef pair<int,int> pint;
int n,q,w[N],b[N],idx[N],lans;
vector<pint> lsh;
struct Sgt{
	int ls,rs,l,r,sum,lmx,rmx;
}a[N<<5];
#define mid ((a[i].l+a[i].r)>>1)
int Sgtl;
inline int new_Sgt(int l,int r){++Sgtl,a[Sgtl].l=l,a[Sgtl].r=r;return Sgtl;}
inline int new_Sgt(int i){a[++Sgtl]=a[i];return Sgtl;}
void push_up(int i){
	a[i].sum=a[a[i].ls].sum+a[a[i].rs].sum;
	a[i].lmx=max(a[a[i].ls].lmx,a[a[i].ls].sum+a[a[i].rs].lmx);
	a[i].rmx=max(a[a[i].ls].rmx+a[a[i].rs].sum,a[a[i].rs].rmx);
}
void build(int i){
	a[i].sum=a[i].lmx=a[i].rmx=a[i].r-a[i].l+1;
	if(a[i].l==a[i].r) return;
	build(a[i].ls=new_Sgt(a[i].l,mid));
	build(a[i].rs=new_Sgt(mid+1,a[i].r));
}
void modify(int i,int p,int x){
	if(a[i].l==a[i].r){a[i].sum=x,a[i].lmx=a[i].rmx=max(0,x);return;}
	modify(mid>=p?(a[i].ls=new_Sgt(a[i].ls)):(a[i].rs=new_Sgt(a[i].rs)),p,x);
	push_up(i);
}
int qsum(int i,int l,int r){
	if(a[i].l>=l && a[i].r<=r) return a[i].sum;
	if(mid>=l) return mid<r?qsum(a[i].ls,l,r)+qsum(a[i].rs,l,r):qsum(a[i].ls,l,r);
	return qsum(a[i].rs,l,r);
}
pint qlmx(int i,int l,int r){
	if(a[i].l>=l && a[i].r<=r) return pint(a[i].sum,a[i].lmx);
	if(mid>=l){
		if(mid<r){
			pint t1=qlmx(a[i].ls,l,r),t2=qlmx(a[i].rs,l,r);
			return pint(t1.first+t2.first,max(t1.second,t2.first+t2.second));
		}
		return qlmx(a[i].ls,l,r);
	}
	return qlmx(a[i].rs,l,r);
}
pint qrmx(int i,int l,int r){
	if(a[i].l>=l && a[i].r<=r) return pint(a[i].sum,a[i].rmx);
	if(mid>=l){
		if(mid<r){
			pint t1=qrmx(a[i].ls,l,r),t2=qrmx(a[i].rs,l,r);
			return pint(t1.first+t2.first,max(t1.second+t2.first,t2.second));
		}
		return qrmx(a[i].ls,l,r);
	}
	return qrmx(a[i].rs,l,r);
}
#undef mid
int rt[N];
signed main(){
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;++i) cin >> w[i];
	lsh.resize(n+1);
	for(int i=1;i<=n;++i) lsh[i]=pint(w[i],i);
	sort(lsh.begin(),lsh.end());
	for(int i=1;i<=n;++i) b[lsh[i].second]=i,idx[i]=lsh[i].second;
	build(rt[1]=new_Sgt(1,n));
	for(int i=2;i<=n;++i) modify(rt[i]=new_Sgt(rt[i-1]),idx[i-1],-1);
	cin >> q;
	while(q--){
		int l1,r1,l2,r2;
		cin >> l1 >> r1 >> l2 >> r2;
		l1=(l1+lans)%n+1,r1=(r1+lans)%n+1,l2=(l2+lans)%n+1,r2=(r2+lans)%n+1;
		if(l1>r1) swap(l1,r1);
		if(l1>l2) swap(l1,l2);
		if(l1>r2) swap(l1,r2);
		if(r1>l2) swap(r1,l2);
		if(r1>r2) swap(r1,r2);
		if(l2>r2) swap(l2,r2);
		int l=1,r=n;
		while(l<r){
			int mid=l+r+1>>1;
			if(qrmx(rt[mid],l1,r1-1).second+qsum(rt[mid],r1,l2)+qlmx(rt[mid],l2+1,r2).second>=0) l=mid;
			else r=mid-1;
		}
		cout << (lans=w[idx[l]]) << '\n';
	}
	return 0;
}