码子如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+2e4;
int a[maxn],c[maxn];
int lc[maxn*32];
int rc[maxn*32];
int lm[maxn*32];
int rm[maxn*32];
int mm[maxn*32];
int sz[maxn*32];
int n,m;
int rt[maxn];
int p[maxn];
int tot=0,ttt=0;
bool cmp(const int &x,const int &y)
{
	return a[x]<a[y];
}
void psup(int x,int ll,int rr)
{
	int mid=(ll+rr)/2;
	sz[x]=sz[lc[x]]+sz[rc[x]];
	lm[x]=lm[lc[x]];rm[x]=rm[rc[x]];
	if(lm[lc[x]]==mid-ll+1)lm[x]+=lm[rc[x]];
	if(rm[rc[x]]==rr-mid)rm[x]+=rm[lc[x]];
	mm[x]=max(max(mm[lc[x]],mm[rc[x]]),rm[lc[x]]+lm[rc[x]]);
}
void modi(int &now,int pre,int ll,int rr,int pos)
{
	if(now==0)now=++ttt;
	int mid=(ll+rr)/2;
	sz[now]=sz[pre]+1;
	if(ll==rr)
	{
		lm[now]=rm[now]=mm[now]=1;
		return;
	}
	if(pos<=mid)modi(lc[now],lc[pre],ll,mid,pos),rc[now]=rc[pre];
	else modi(rc[now],rc[pre],mid+1,rr,pos),lc[now]=lc[pre];
	psup(now,ll,rr);
}
int que(int now,int ll,int rr,int L,int R)
{
	if(L==ll&&rr==R)return mm[now];
	int mid=(ll+rr)/2;
	if(R<=mid)return que(lc[now],ll,mid,L,R);
	if(mid<L)return que(rc[now],mid+1,rr,L,R);
	return max(max(que(lc[now],ll,mid,L,mid),que(rc[now],mid+1,rr,mid+1,R)),min(lm[rc[now]],R-mid)+min(rm[lc[now]],mid-L+1));
}
int main()
{
	int i,aa,bb,cc;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
//		modi(rt[i],rt[i-1],0,1e9,a[i],i);
		c[i]=a[i];
		p[i]=i;
	}
	sort(c+1,c+n+1);
	int len=unique(c+1,c+n+1)-c-1;
	for(i=1;i<=n;i++)a[i]=lower_bound(c+1,c+len+1,a[i])-c;
	sort(p+1,p+n+1,cmp);
	for(i=n;i>=1;i--)
		if(a[p[i]]!=a[p[i+1]])modi(rt[a[p[i]]],rt[a[p[i+1]]],1,n,p[i]);
		else modi(rt[a[p[i]]],rt[a[p[i]]],1,n,p[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&aa,&bb,&cc);
		int l=1,r=len,mid,ans=1;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(mid==2)
				int my=-1;
			if(que(rt[mid],1,n,aa,bb)>=cc)ans=mid,l=mid+1;
			else r=mid-1;
		}
		cout<<c[ans]<<endl;
	}
	return 0;
}