#include<bits/stdc++.h>
using namespace std;
int n,m,a[4000101],nxt=1,mp[4000101],tree[4000101];
struct node{
	int l,r,num,ans;
}q[4000101];
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'&&ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch-'0');
		ch=getchar();
	}
	return x;
}
bool cmp1(node p,node q){return p.r<q.r;}
bool cmp2(node p,node q){return p.num<q.num;}
int lowbit(int x){return x&-x;}
void add(int x,int t){
	for(;x<=n;x+=lowbit(x))tree[x]+=t;
}
int query(int x){
	int sum=0;
	for(;x;x-=lowbit(x))sum+=tree[x];
	return sum;
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	m=read();
	for(int i=1;i<=m;i++){
		q[i].l=read();
		q[i].r=read();
		q[i].num=i;
	}
	sort(q+1,q+m+1,cmp1);
	for(int hyh=1;hyh<=m;hyh++){
		for(int i=nxt;i<=q[hyh].r;i++){
			if(mp[a[i]])add(mp[a[i]],-1);
			add(i,1);
			mp[a[i]]=i;
		}
		q[hyh].ans=query(q[hyh].r)-query(q[hyh].l-1);
		nxt=q[hyh].r+1;
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++)printf("%lld\n",q[i].ans);
	return 0;
}

RE是什么鬼