#include<bits/stdc++.h>
using namespace std;
int n,m,x,a[40000005][3],b[1000005],cnt=0,c[1000005],y;
int read()
{
	int result=0;
	char ch=getchar();
	while (ch<'0' || ch>'9')
	ch=getchar();
	while ('0'<=ch && ch<='9')
	{
		result=result*10+(ch^48);
		ch=getchar();
	}
	return result;
}
int build(int l,int r)
{
	int x=++cnt;
	if (l<r)
	{
		int mid=l+r>>1;
		a[x][1]=build(l,mid);
		a[x][2]=build(mid+1,r);
	}
	return x;
}
int modify(int x,int bl,int br,int y,int z)
{
	++cnt;
	memcpy(a[cnt],a[x],sizeof(a[x]));
	x=cnt;
	if (bl==br)
	a[x][0]=z;
	else
	{
		int mid=bl+br>>1;
		if (y<=mid)
		a[x][1]=modify(a[x][1],bl,mid,y,z);
		else
		a[x][2]=modify(a[x][2],mid+1,br,y,z);
		a[x][0]=a[a[x][1]][0]+a[a[x][2]][0];
	}
	return x;
}
int query(int x,int bl,int br,int l,int r)
{
	if (l<=bl && br<=r)
	return a[x][0];
	int mid=bl+br>>1,result=0;
	if (l<=mid)
	result+=query(a[x][1],bl,mid,l,r);
	if (mid<r)
	result+=query(a[x][2],mid+1,br,l,r);
	return result;
}
int main()
{
	n=read();
	build(1,n);
	b[0]=1;
	for (int i=1;i<=n;++i)
	{
		x=read();
		if (c[x])
		b[i]=modify(modify(b[i-1],1,n,i,1),1,n,c[x],0);
		else
		b[i]=modify(b[i-1],1,n,i,1);
		c[x]=i;
	}
	m=read();
	while (m--)
	{
		x=read();
		y=read();
		cout<<query(b[y],1,n,x,y)<<'\n';
	}
}