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

struct node {
	int l,r,b,id;
} p[100001],P2[100001];
int tot=0;
vector<node> P3[66];
int a[100001],cnt[100001],ANS[100001],S;
const ll w=64,w2=6,w3=63,lim=100000;
unsigned ll pre[66],suf[66];
struct Bitset {
	vector<unsigned ll> vs;
	ll n;
	inline void init(ll len) {
		vs.resize((len>>w2)+1);
		n=len;
	}
	inline void operator&=(Bitset B) {
		if (B.n<n)n^=B.n^=n^=B.n,swap(B.vs,vs);
		for (ll i=0; i<=(n>>w2); i++) {
			vs[i]&=B.vs[i];
		}
	}
	inline void set0(ll x) {
		vs[x>>w2]&=~(1ull<<(x&w3));
	}
	inline void set1(ll x) {
		vs[x>>w2]|=(1ull<<(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++)if (vs[i])return 1;
		return 0;
	}
	inline void all() {
		for (ll i=0; i<(n>>w2); i++) {
			vs[i]=~0;
		}
		vs[n>>w2]=pre[n&w3];
	}
	inline ll mex() {
		ll ans=0;
		for (ll i=0; i<=(n>>w2); i++) {
			if (!(~vs[i])){
				ans+=w;
			}else{
				ans+=__builtin_ctzll(~vs[i]);
				break;
			}
		}
		return ans;
	}
} bs,bs2[66];
ll T=0;

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

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

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

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

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            #define SIZE (1<<25)
            char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(p3=out,1,SIZE,stdout))
            #define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        template<typename type>
        inline void read(type &x)
        {
            x=0;char ch=getchar();
            while(!isdigit(ch)) ch=getchar();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        }
        template<typename type>
        inline void write(type x)
        {
            static short Stack[50],top(0);
            do Stack[++top]=x%10,x/=10;while(x);
            while(top) putchar(Stack[top--]|48);
            putchar(' ');
        }
        #ifndef LOCAL
            #undef SIZE
            #undef getchar
            #undef putchar
            #undef flush
        #endif
    }
}using namespace ly::IO;

int main() {
	ll n;
	read(n);
	for (ll i=1; i<=n; i++) {
		read(a[i]);
	}
	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;
	read(q);
	for (ll i=1; i<=q; i++) {
//		p[i].l=read(),p[i].r=read(),p[i].b=read();
		read(p[i].l);read(p[i].r);read(p[i].b);
		p[i].id=i;
		if (p[i].b<=w) {
			P3[p[i].b].push_back(p[i]);
		} else {
			P2[++tot]=p[i];
		}
	}
	if (tot) {
		S=n/sqrt(tot)+1;
		sort(P2+1,P2+1+tot,[&](node a,node b) {
			if (a.l/S==b.l/S){
				if ((a.l/S)&1)return a.r>b.r;
				else return a.r<b.r;
			}else{
				return a.l<b.l;
			}
		});
		ll L=1,R=0;
		bs.init(lim);
		for (ll i=1; i<=tot; i++) {
			int l=P2[i].l,r=P2[i].r,b=P2[i].b;
			while (L>l)add(--L);
			while (R<r)add(++R);
			while (L<l)del(L++);
			while (R>r)del(R--);
			Bitset ans;
			ans.init(b-1);
			ans.all();
			ll rel=0;
			for (ll j=1;; ++j) {
				ans&=bs.sub((j-1)*b,min(lim,j*b-1));
				if (!ans.any()) {
					rel=j-1;
					break;
				}
			}
			ANS[P2[i].id]=rel;
		}
	}

	for (ll i=1; i<=w; ++i) {
		if (P3[i].empty())continue;
		S=n/sqrt(P3[i].size())+1;
		T=i;
		for (ll j=0; j<=lim; j++)cnt[j]=0;
		sort(P3[i].begin(),P3[i].end(),[&](node a,node b) {
			if (a.l/S==b.l/S){
				if ((a.l/S)&1)return a.r>b.r;
				else return a.r<b.r;
			}else{
				return a.l<b.l;
			}
		});
		for (ll j=0; j<i; j++) {
			bs2[j].init(lim/i);
			for (unsigned ll &k:bs2[j].vs) {
				k=0;
			}
		}
		ll L=1,R=0;
		for (ll j=0; j<P3[i].size(); ++j) {
			ll l=P3[i][j].l,r=P3[i][j].r;
			while (L>l)add1(--L);
			while (R<r)add1(++R);
			while (L<l)del1(L++);
			while (R>r)del1(R--);
			for (ll k=0; k<i; ++k) {
				ANS[P3[i][j].id]=max(ANS[P3[i][j].id],(int)bs2[k].mex());
			}
		}
	}
	for (ll i=1; i<=q; i++)write(ANS[i]);
	return 0;
}

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