#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1000052;
ll n,m,pos[N],pre[N],last[N],nxt[N],ans[N],cnt,l,r,a[N],res;
struct node{
	ll l,r,k;
	inline bool operator < (const node &x)const{
		if(pos[l] != pos[x.l]) return pos[l]<pos[x.l];
		if(pos[l] & 1)
			return r<x.r;
		return r>x.r;
	}
}xu[N];
inline ll read()
{
	ll x=0;int b=1;char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-') b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*b;
}
//inline bool cmp(node x,node y)
//{
//	return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];
//}
signed main()
{
	n=read();cnt=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		pos[i]=i/cnt;
	}
	m=read();
	for(int i=1;i<=m;++i)
	{
		xu[i].l=read();xu[i].r=read();
		xu[i].k=i;
	}
	sort(xu+1,xu+1+m);
	memset(last,N,sizeof(last));
	for(int i=1;i<=n;++i)
	{
		pre[i]=last[a[i]];
		last[a[i]]=i;
		if(pre[i]>=0) nxt[pre[i]]=i;
		nxt[i]=n;
	}
	l=1;r=0;res=0;
	for(int i=1;i<=m;++i)
	{
		while(xu[i].l<l) res+=(r<nxt[--l]);
		while(xu[i].r>r) res+=(l>pre[++r]);
		while(xu[i].l>l) res-=(r<nxt[l++]);
		while(xu[i].r<r) res-=(l>pre[r--]);
		ans[xu[i].k]=res;
	}
	for(int i=1;i<=m;++i)
		printf("%lld\n",ans[i]);
	return 0;
}

谢谢