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

const int N=1e6+10;
int n,a[N],pre[N],v[N],ans[N],c[N],qq;

struct T
{
	int id,l,r;
}q[N];

bool cmp(T a,T b)
{
	return a.r<b.r;
}

int add(int x,int y)
{
	for(;x<=n;x+=x&-x)c[x]+=y;
}

int ask(int x)
{
	int ans=0;
	for(;x;x-=x&-x)ans+=c[x];
	return ans;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		pre[i]=v[a[i]];
		v[a[i]]=i;
	}
//	for(int i=1;i<=n;i++)cout<<pre[i]<<endl;
	scanf("%d",&qq);
	for(int i=1;i<=qq;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
//	for(int i=1;i<=qq;i++)cout<<q[i].l<<" "<<q[i].r<<" "<<q[i].id<<endl;
	
	sort(q+1,q+1+qq,cmp);
//	cout<<1<<" "<<q[1].id<<endl;
	int l=1;
	for(int i=1;i<=qq;i++)
	{
		int r=q[i].r;
		while(l<=r)
		{
			if(pre[l])add(pre[l],-1);
			add(l,1);
			l++;
		}
//		cout<<"fdsaf";
		ans[q[i].id]=ask(q[i].r)-ask(q[i].l-1);
	}
	for(int i=1;i<=qq;i++)
	{
		cout<<ans[i]<<"\n";
	}
	return 0;
}