#include<bits/stdc++.h>
#define int long long
#define N 1000002
#define lyl p<<1
#define lyr p<<1|1
using namespace std;
int n,m,a[N],flag[N],ans[N];
vector<int>v[N];
struct hq{
	int l,r,id;
}q[N];
struct ly{
	int l,r;
	int ok;
}tr[N*4];
bool cmp(hq a,hq b){
	return a.r<b.r;
}
void pushup(int p){
	tr[p].ok=tr[lyl].ok+tr[lyr].ok;
	return;
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].ok=1;
		return ;
	}
	int mid=l+r>>1;
	build(lyl,l,mid);
	build(lyr,mid+1,r);
	pushup(p);
	return ;
}
void change(int p,int x){
	if(x==tr[p].l&&tr[p].l==tr[p].r){
		tr[p].ok=0;
		return ;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(x<=m)change(lyl,x);
	else change(lyr,x);
	pushup(p);
	return;
}
int liu(int p,int l,int r){
	if(l<=tr[p].l&&r>=tr[p].r){
		return tr[p].ok;
	}
	int sum=0;
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)sum+=liu(lyl,l,r);
	if(r>mid)sum+=liu(lyr,l,r);
	return sum;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
    }
	sort(q+1,q+1+m,cmp);
	for(int i=1;i<=m;i++){
		v[q[i].r].push_back(i);
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		if(flag[a[i]])change(1,flag[a[i]]);
		flag[a[i]]=i;
		for(auto sr:v[i]){
			ans[q[sr].id]=liu(1,q[sr].l,q[sr].r);
		}
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}/*6
1 2 3 4 3 5
3
1 2
3 5
2 6*/