#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+5;
struct qwe{
	int l,r,id;
}tr[N];
int n,m,a[N],l,c[N],ans[N];
int b[N];
int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x>>3)+(x>>1)+ch-'0',ch=getchar();
	return x; 
}
bool mm(qwe a,qwe b){
	return a.r<b.r;
}
void add(int x,int y){
	for(;x<=n;x+=x&(-x)) c[x]+=y;
}
int summ(int x){
	int ans=0;
	for(;x;x-=x&(-x)) ans+=c[x];
	return ans;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	m=read();
	for(int i=1;i<=m;i++) tr[i].l=read(),tr[i].r=read(),tr[i].id=i;
	sort(tr+1,tr+1+m,mm);
	for(int i=1;i<=m;i++){
		for(int j=l+1;j<=tr[i].r;j++){
			if(b[a[j]]) add(b[a[j]],-1);	
			b[a[j]]=j;
			add(j,1);
		}
		l=tr[i].r;
		ans[tr[i].id]=summ(tr[i].r)-summ(tr[i].l-1);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}