整体二分，TLE了

#include<iostream>
#include<cstdio>
#include<algorithm>
#define re register int
#define il inline
using namespace std;
const int N=5e4+10;
int n,m,a[N],b[N],tot,ans[N],c[N],sum[N][3];
struct Node{
	int l1,r1,l2,r2,id;
}q[N],q1[N],q2[N];
int tree[N<<2][3];
il void build(int k,int l,int r){
	if(l==r){
		tree[k][0]=c[l];
		tree[k][1]=sum[l][1];
		tree[k][2]=sum[l][2];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k][0]=tree[k<<1][0]+tree[k<<1|1][0];
	tree[k][1]=max(tree[k<<1][1],tree[k<<1|1][1]);
	tree[k][2]=max(tree[k<<1][2],tree[k<<1|1][2]);
}
il int Ask(int k,int l,int r,int L,int R,int op){
	if(l>=L&&r<=R)return tree[k][op];
	if(l>R||r<L){
		if(op==0)return 0;
		return -11451419;
	}
	int mid=(l+r)>>1;
	if(op==0){
		int res=0;
		if(L<=mid)res+=Ask(k<<1,l,mid,L,R,op);
		if(R>mid)res+=Ask(k<<1|1,mid+1,r,L,R,op);
		return res;
	}
	int res=-11451419;
	if(L<=mid)res=max(res,Ask(k<<1,l,mid,L,R,op));
	if(R>mid)res=max(res,Ask(k<<1|1,mid+1,r,L,R,op));
	return res;
}
il void solve(int l,int r,int L,int R){
	if(L>R)return;
	if(l>r){
		for(re i=L;i<=R;i++)
			ans[q[i].id]=b[r];
		return;
	}
	int mid=(l+r)>>1;
	for(re i=1;i<=n;i++){
		if(a[i]>=b[mid])c[i]=1;
		else c[i]=-1;
		sum[i][1]=sum[i-1][1]+c[i];
	}
	for(re i=n;i>=1;i--)sum[i][2]=sum[i+1][2]+c[i];
	build(1,1,n);
	int lt=0,rt=0;
	for(re i=L;i<=R;i++){
		int S=Ask(1,1,n,q[i].l1,q[i].r1,2)+Ask(1,1,n,q[i].r1+1,q[i].l2-1,0)+Ask(1,1,n,q[i].l2,q[i].r2,1)-sum[q[i].l2-1][1]-sum[q[i].r1+1][2];
//		cout<<S<<" "<<b[mid]<<" "<<q[i].id<<endl;
		if(S>=0){ //可以 
			rt++;
			q2[rt]=q[i];
		}
		else{
			lt++;
			q1[lt]=q[i];
		}
	}
	for(re i=1;i<=lt;i++)q[L+i-1]=q1[i];
	for(re i=lt+1;i<=lt+rt;i++)q[L+i-1]=q2[i-lt];
	solve(l,mid-1,L,L+lt-1);
	solve(mid+1,r,L+lt,R);
}
int main(){
	scanf("%d",&n);
	for(re i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	tot=1;
	for(re i=2;i<=n;i++){
		if(b[i]!=b[tot]){
			tot++;
			b[tot]=b[i];
		}
	}
	scanf("%d",&m);
	for(re i=1;i<=m;i++){
		scanf("%d%d%d%d",&q[i].l1,&q[i].r1,&q[i].l2,&q[i].r2);
		q[i].id=i;
	}
	solve(1,tot,1,m);
	for(re i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}