#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1ll)
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
int a[N],root[N],tmp[N],tot = 0,t;
vector<int> v[N]; 
int n,m;
struct node{
	ll rsum,lsum,sum,ans;
	int lson,rson;
}tree[N<<5];
int build(int l,int r){
	int p = ++tot;
	if(l == r){
		tree[p].sum = 1ll;
		tree[p].lsum = 1ll;
		tree[p].rsum = 1ll;
		tree[p].ans = 1ll;
		return p;
	}
	tree[p].lson = build(l,mid);
	tree[p].rson = build(mid+1ll,r);
	tree[p].lsum = max(tree[tree[p].lson].lsum,tree[tree[p].lson].sum + tree[tree[p].rson].lsum);
	tree[p].rsum = max(tree[tree[p].rson].rsum,tree[tree[p].rson].sum + tree[tree[p].lson].rsum);
	tree[p].sum = tree[tree[p].lson].sum + tree[tree[p].rson].sum;
	tree[p].ans = max(max(tree[tree[p].lson].ans,tree[tree[p].rson].ans),tree[tree[p].lson].rsum + tree[tree[p].rson].lsum);
	return p;
}
bool cmp(int A,int B){
	return A < B;
}
int change(int now,int x,int l,int r){
//	cerr<<"now:"<<now<<endl;
	int p = ++ tot;
	tree[p] = tree[now];
	if(l == r){
		tree[p].sum = -INF;
		tree[p].lsum = -INF;
		tree[p].rsum = -INF;
		tree[p].ans = -INF;
		return p;
	}
	if(x <= mid){
		tree[p].lson = change(tree[now].lson,x,l,mid);
	}else{
		tree[p].rson = change(tree[now].rson,x,mid+1ll,r);
	}
	tree[p].lsum = max(tree[tree[p].lson].lsum,tree[tree[p].lson].sum + tree[tree[p].rson].lsum);
	tree[p].rsum = max(tree[tree[p].rson].rsum,tree[tree[p].rson].sum + tree[tree[p].lson].rsum);
	tree[p].sum = tree[tree[p].lson].sum + tree[tree[p].rson].sum;
	tree[p].ans = max(max(tree[tree[p].lson].ans,tree[tree[p].rson].ans),tree[tree[p].lson].rsum + tree[tree[p].rson].lsum);
	return p;
}
node query(int now,int l,int r,int ll,int rr){
//	cerr<<"NOW:"<<now<<endl;
//	cerr<<"l:"<<l<<endl;
//	cerr<<"r:"<<r<<endl;
//	cerr<<"ll:"<<ll<<endl;
//	cerr<<"rr:"<<rr<<endl;
//	exit(0);
	if(ll == l && rr == r){
		return tree[now];
	}
	if(rr <= mid){
		return query(tree[now].lson,l,mid,ll,rr);
	}else if(ll > mid){
		return query(tree[now].rson,mid+1ll,r,ll,rr);
	}else{
		node ln = query(tree[now].lson,l,mid,ll,mid);
		node rn = query(tree[now].rson,mid+1ll,r,mid+1ll,rr);
		node ans;
		ans.lsum = max(ln.lsum,ln.sum + rn.lsum);
		ans.rsum = max(rn.rsum,ln.sum + ln.rsum);
		ans.sum = rn.sum + ln.sum;
		ans.ans = max(max(ln.ans,rn.ans),ln.rsum + rn.lsum);
		
		return ans;
	}
}
int solve(int ll,int rr,int k){
	int l = 1ll,r = t;
	while(l < r){
		int Mid = (l+r+1ll)>>1ll;
//		cerr<<"MID:"<<Mid<<endl;
//		cerr<<"t:"<<t<<endl;
//		cerr<<"root:"<<root[Mid]<<endl;
		int q = query(root[Mid],1,n,ll,rr).ans;
//		cerr<<"QUERY:"<<q<<endl;
		if(q >= k){
			l = Mid;
		}else{
			r = Mid-1ll;
		}
//		cerr<<tmp[l+1]<<endl;
	}
	return tmp[l];
}
signed main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		tmp[i] = a[i];
	}
	sort(tmp+1,tmp+1+n,cmp);
	t = unique(tmp+1,tmp+1+n)-tmp-1ll;
	for(int i=1;i<=n;i++){
		a[i] = lower_bound(tmp+1,tmp+1+t,a[i])-tmp;
		v[a[i]].push_back(i);
	}
	root[1] = build(1ll,n);
	for(int i=2;i<=t;i++){
		root[i] = root[i-1];
		for(int j=0;j<v[i-1].size();j++){
			root[i] = change(root[i],v[i-1][j],1ll,n);
		}
	}
	scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		int l,r,k;
		scanf("%lld%lld%lld",&l,&r,&k);
		printf("%lld\n",solve(l,r,k));
	}
}