#include <bits/stdc++.h>
#define f(c,a,b) for(c=a;c<=b;++c)
#define fd(c,a,b)for(c=b;c>=a;--c)
#define ll unsigned long long
#define mp make_pair
#define il inline
#define ri register
#define co const
using namespace std;
const int N=3e5+5;
int n,m,k,i,j;

il int read() {
	ri int ans=0;
	ri char c=getchar();
	ri bool neg=0;
	while(!isdigit(c)) neg|=(c=='-'),c=getchar();
	while(isdigit(c)) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
	return neg?-ans:ans;
}
il void write(ri int x) {
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
il void writes(ri int x){write(x);putchar(' ');}
il void writed(ri int x){write(x);putchar('\n');}
int S;
int t[N],a[N],cnt[N];
struct node{
	int l,r;
	int id,ans;
}q[N];
inline bool cmp(node a,node b) {
	return (t[a.l] != t[b.l]) ? t[a.l] < t[b.l] : ((t[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
il void solve(){
    n=read();
	S=sqrt(n);
	f(i,1,n) t[i]=i/S;
	f(i,1,n) a[i]=read();
	m=read();
	f(i,1,m) q[i].id=i,q[i].l=read(),q[i].r=read();
	int l=1,r=0,now=0;
	sort(q+1,q+1+m,cmp);
	f(i,1,m){
		int L=q[i].l,R=q[i].r;
		while(l<L) now-=!--cnt[a[l++]];
		while(l>L) now+=!cnt[a[--l]]++;
		while(r<R) now+=!cnt[a[++r]]++;
		while(r>R) now-=!--cnt[a[r--]];
		q[q[i].id].ans=now;
	}
	f(i,1,m)  writed(q[i].ans);
    return;
}

signed main() {
	solve();
	return 0;
}