#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
struct node{
	int l,r,k;
}q[N];
int pos[N],ans[N],cnt[N],a[N];
int Ans=0;
inline bool cmp(node a,node b) 
{
	if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
	if(pos[a.l]&1) return a.r>b.r;
	return a.r<b.r;
	if(a.l==b.l) return a.r<b.r;
	return a.l<b.l; 
}
inline void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1) Ans++;
}
inline void del(int x)
{
	cnt[a[x]]--;
	if(cnt[a[x]]==0) Ans--;
}
int main()
{
	int n;
	scanf("%d",&n);
	int block=sqrt(n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		pos[i]=(i-1)/block+1;
	}
	int m;scanf("%d",&m);
	for(int i=1;i<=m;i++) {
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].k=i;	
	}
	sort(q+1,q+1+m,cmp) ;
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].l) del(l++);
		while(r>q[i].r) del(r--);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		ans[q[i].k]=Ans;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}