#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct node {
	ll l,r,b,id;
} p[100005],P2[100005];
ll tot=0;
vector<node> P3[100005];
ll a[100005],cnt[100005],ANS[100005],S;
const ll w=64,w2=6,w3=63,lim=100000;
unsigned ll pre[88],suf[88];
struct Bitset {
	vector<unsigned ll> vs;
	ll n;
	inline void init(ll len) {
		vs.resize((len>>w2)+5);
		n=len;
	}
	friend Bitset operator&(Bitset A,Bitset B) {
		Bitset C;
		C.init(max(A.n,B.n));
		for (ll i=0; i<=(min(A.n,B.n)>>w2); i++) {
			C.vs[i]=A.vs[i]&B.vs[i];
		}

		return C;
	}
	inline ll operator[](ll x) {
		return vs[x>>w2]>>(x&w3)&1;
	}

	inline void set(ll x,ll v) {
		vs[x>>w2]-=(vs[x>>w2]>>(x&w3)&1)<<(x&w3);
		vs[x>>w2]+=v<<(x&w3);
	}
	inline ll subcut(ll l,ll r) {
		if ((l>>w2)==(r>>w2)) {
			return ((pre[r&w3]-(!(l&w3)?0:pre[(l&w3)-1]))&vs[l>>w2])>>(l&w3);
		} else {
			return ((suf[l&w3]&vs[l>>w2])>>(l&w3))|((pre[r&w3]&vs[r>>w2])<<(w-(l&w3)));
		}
	}
	inline Bitset sub(ll l,ll r) {
		Bitset C;
		C.init(max(0ll,r-l+1));
		if (r-l+1<=0)return C;
		ll pl=l;
		for (ll i=0; i<=((r-l+1)>>w2); i++) {
			C.vs[i]=subcut(pl,min(r,pl+w-1));
			pl+=w;
		}
		return C;
	}
	inline bool any() {
		for (ll i=0; i<=(n>>w2); i+=4)if (vs[i]|vs[i+1]|vs[i+2]|vs[i+3])return 1;
		return 0;
	}
	inline void all() {
		for (ll i=0; i<(n>>w2); i++) {
			vs[i]=pre[w-1];
		}
		vs[n>>w2]=pre[n&w3];
	}
	inline ll mex() {
		
		ll ans=0;
		for (ll i=0; i<=(n>>w2); i++) {
			ll z=w;
			if ((~vs[i])!=0)
			z=__builtin_ctzll(~vs[i]);
			ans+=z;
			if (z!=w)break;
		}
		return min(n+1,ans);
	}
} bs,bs2[66];
ll T=0;

inline void add(ll pos) {
	cnt[a[pos]]++;
	if (cnt[a[pos]]==1) {
		bs.set(a[pos],1);
	}
}

inline void del(ll pos) {
	cnt[a[pos]]--;
	if (cnt[a[pos]]==0) {
		bs.set(a[pos],0);
	}
}

inline void add1(ll pos) {
	cnt[a[pos]]++;
	if (cnt[a[pos]]==1) {
		bs2[a[pos]%T].set(a[pos]/T,1);
	}
}

inline void del1(ll pos) {
	cnt[a[pos]]--;
	if (cnt[a[pos]]==0) {
		bs2[a[pos]%T].set(a[pos]/T,0);
	}
}

inline ll read() {
	ll x=0;
	char c=getchar();
	while(!isdigit(c))c=getchar();
	while (isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	n=read();
	for (ll i=1; i<=n; i++) {
		a[i]=read();
	}
	for (ll i=0; i<w; i++) {
		if (i==0) {
			pre[i]=(1ull<<i);
		} else {
			pre[i]=pre[i-1]+(1ull<<i);
		}
	}
	for (ll i=w-1; i>=0; i--) {
		suf[i]=suf[i+1]+(1ull<<i);
	}
	ll q;
	q=read();
	S=sqrt(max(1ll,n));
	for (ll i=1; i<=q; i++) {
		p[i].l=read(),p[i].r=read(),p[i].b=read();
		p[i].id=i;
		if (p[i].b<=30) {
			P3[p[i].b].push_back(p[i]);
		} else {
			P2[++tot]=p[i];
		}
	}
	sort(P2+1,P2+1+tot,[&](node a,node b) {
		return (a.l/S==b.l/S?a.r<b.r:a.l<b.l);
	});
	ll L=1,R=0;
	bs.init(lim);
	for (ll i=1; i<=tot; i++) {
//		cout<<p[i].l<<" "<<p[i].r<<"------------\n";
		while (L>P2[i].l)add(--L);
		while (R<P2[i].r)add(++R);
		while (L<P2[i].l)del(L++);
		while (R>P2[i].r)del(R--);
		Bitset ans;
		ans.init(P2[i].b-1);
		ans.all();
		ll rel=lim/P2[i].b+1;
		for (ll j=1; j<=lim/P2[i].b+1; j++) {
			Bitset A=bs.sub((j-1)*P2[i].b,min(lim,j*P2[i].b-1));
			ans=ans&A;
			if (!ans.any()) {
				rel=j-1;
				break;
			}
		}
		ANS[P2[i].id]=rel;
	}
	for (ll i=1; i<=w; i++) {
		T=i;
		for (ll j=0; j<i; j++) {
			bs2[j].init(lim/i);
		}
		for (ll j=0;j<=lim;j++)cnt[j]=0,bs2[j%i].set(j/i,0);
		sort(P3[i].begin(),P3[i].end(),[&](node a,node b) {
			return (a.l/S==b.l/S?a.r<b.r:a.l<b.l);
		});
		
		ll L=1,R=0;
		for (ll j=0; j<P3[i].size(); j++) {
			while (L>P3[i][j].l)add1(--L);
			while (R<P3[i][j].r)add1(++R);
			while (L<P3[i][j].l)del1(L++);
			while (R>P3[i][j].r)del1(R--);
			for (ll k=0; k<P3[i][j].b; k++) {
				ANS[P3[i][j].id]=max(ANS[P3[i][j].id],bs2[k].mex());
			}
		}
	}
	for (ll i=1; i<=q; i++)cout<<ANS[i]<<"\n";
	return 0;
}

/*
2
49999 99999
1
1 2 49999
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/