#include<bits/stdc++.h>
using namespace std;
int cur;
const int N=2e5+5;
const int M=1e6+5; 
const int L=1e6+6;
long long a[M],ans[M],cnt[M];
int n,m,num=1;
long long l=1,r;
struct node{
	int l,r,id;
}p[N];
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
bool cmp(node a,node b){
	return (a.l/num)^(b.l/num)?a.l<b.l:((a.l/num)&1)?a.r<b.r:a.r>b.r;
}
void add(int x){
	if(cnt[a[x]]==0){
		cur++;
	}
	cnt[a[x]]++;
}
void del(int x){ 
	cnt[a[x]]--;
	if(cnt[a[x]]==0){
		cur--;
	}
}
void modui(){
	for(int i=1;i<=m;i++){
		while(l<p[i].l){
			del(l++);
		}
		while(r<p[i].r){
			add(++r);
		}
		while(l>p[i].l){
			add(--l);
		}
		while(r>p[i].r){
			del(r--);
		}
		ans[p[i].id]=cur;
	}
}
void Init(){ 
	n=read();
	//memset(cnt,0,sizeof(cnt));
	num=(int)sqrt(n);
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	m=read();
	for(int i=1;i<=m;i++){
		p[i].l=read();
		p[i].r=read();
		p[i].id=i;
	}
	sort(p+1,p+m+1,cmp);
}
int main(){
	Init();
	modui();
	for(int i=1;i<=m;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}