#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

int n,a[maxn],d[maxn<<5],lc[maxn<<5],rc[maxn<<5],nex[maxn],las[maxn],rt[maxn<<5],m,num;

inline int read(){
    int x=0,f=1;
	char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int build(int s,int t){
	int p=++num;
	if(s==t)	return p;
	int mid=s+t>>1;
	lc[p]=build(s,mid);
	rc[p]=build(mid+1,t);
	return p;
}

void Pushup(int p){
	d[p]=d[lc[p]]+d[rc[p]];
}

int update(int s,int t,int pre,int pos){
	int p=++num;
	lc[p]=lc[pre];
	rc[p]=rc[pre];
	d[p]=d[pre]+1;
	if(s==t)	return p;
	int mid=s+t>>1;
	if(pos<=mid)	lc[p]=update(s,mid,lc[p],pos);
	else			rc[p]=update(mid+1,t,rc[p],pos);
	Pushup(p);
	return p;
}

int query(int s,int t,int p,int l,int r){
	if(!p)	return 0;
	if(l<=s && r>=t)	return d[p];
	int mid=s+t>>1,tot=0;
	Pushup(p);
	if(l<=mid)		tot+=query(s,mid,lc[p],l,r);
	if(r>mid)		tot+=query(mid+1,t,rc[p],l,r);
	return tot;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)	a[i]=read(),nex[i]=n+1;
	for(int i=1;i<=n;i++){
		if(las[a[i]]!=0)	nex[las[a[i]]]=i;
		las[a[i]]=i;
	}
	rt[0]=build(1,n+1);
	for(int i=1;i<=n;i++)	rt[i]=update(1,n+1,rt[i-1],nex[i]);
	m=read(),n++;
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		printf("%d\n",query(1,n,t[r],r+1),n)-query(1,n,rt[l-1],r+1,n));
	}
	return 0;
}