前置题目
const int N=1e5+5;
int n,m,_;
int i,j,k;
struct Step
{
int c,id;
bool operator<(Step &o){
return c<o.c;
}
}a[N];
struct Node
{
int l,r,len;
int sum,lsum,rsum;
void update(int x){
sum=lsum=rsum=x;
}
void init(int x){ len=x; }
Node(int lsum=0,int rsum=0,int sum=0):sum(sum),lsum(lsum),rsum(rsum){ len=0; }
Node operator+(Node b){
return (Node){
lsum==len?len+b.lsum:lsum,
b.rsum==b.len?b.len+rsum:b.rsum,
max(max(sum,b.sum),rsum+b.lsum)
};
}
}t[N<<5];
int root[N],tot=0;
void push_up(int x)
{
int lson=t[x].l,rson=t[x].r;
t[x].len=t[lson].len+t[rson].len;
t[x].sum=max(t[lson].sum,t[rson].sum);
if(t[lson].lsum==t[lson].len) t[x].lsum=max(t[lson].lsum,t[lson].len+t[rson].lsum);
else t[x].lsum=t[lson].lsum;
if(t[rson].rsum==t[rson].len) t[x].rsum=max(t[rson].rsum,t[rson].len+t[lson].rsum);
else t[x].rsum=t[rson].rsum;
t[x].sum=max(t[x].sum,t[lson].rsum+t[rson].lsum);
}
void build(int l,int r,int &x)
{
x=++tot;
t[x].init(r-l+1);
if(l==r) t[x].update(1);
else{
int mid=l+r>>1;
build(l,mid,t[x].l);
build(mid+1,r,t[x].r);
push_up(x);
}
}
void update(int &x,int y,int l,int r,int pos)
{
x=++tot;
t[x]=t[y];
if(l==r) t[x].update(0);
else{
int mid=l+r>>1;
if(mid>=pos) update(t[x].l,t[y].l,l,mid,pos);
else update(t[x].r,t[y].r,mid+1,r,pos);
push_up(x);
}
}
int query(int x,int l,int r,int len,int L,int R)
{
if(L>=l && r>=R) return t[x].sum;
else{
int mid=L+R>>1;
int ans=0;
if(mid>=l) ans=max(ans,query(t[x].l,l,r,len,L,mid));
if(r>=mid+1) ans=max(ans,query(t[x].r,l,r,len,mid+1,R));
ans=max(ans,min(mid-l+1,t[t[x].l].rsum)+min(r-mid,t[t[x].r].lsum));
return ans;
}
}
bool C(int x,int l,int r,int len)
{
int ans=query(root[x],l,r,len,1,n);
return ans>=len;
}
int main()
{
while(~sd(n)){
for(int i=1;i<=n;i++) sd(a[i].c),a[i].id=i;
sort(a+1,a+1+n);
//forn(i,1,n) dbg(a[i].id);
build(1,n,root[1]);
for(int i=2;i<=n;i++){
update(root[i],root[i-1],1,n,a[i-1].id);
}
sd(m);
for(int i=1;i<=m;i++){
int x,y,k;
sddd(x,y,k);
int l=1,r=n,ans=-1;
while(r>=l){
int mid=l+r>>1;
if(C(mid,x,y,k)) l=mid+1,ans=mid;
else r=mid-1;
//dbg(mid);
}
//dbg(ans);
pd(a[ans].c);
}
}
//PAUSE;
return 0;
}