RT.

#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
const int N=1e6+5;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline int read(){
   	int x=0;bool sgn=0;char ch=gt();
   	while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
   	while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
	return sgn?-x:x;
}
template<class T>
inline void print(T x){
	static char st[70];short top=0;
	if(x<0)pt('-');
    do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
	static char st[70];short top=0;
	if(x<0)pt('-');
    do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
	static char st[70];short top=0;
	if(x<0)pt('-');
    do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
	int siz=s.size();
	for(int i=0;i<siz;++i) pt(s[i]);
	printf("\n");
}
int n,m,a[N],zh[N],fu[N],idzh[N],idfu[N],lst[N],pos[N],ans[N];
inline int lowbit(int x){return x&-x;}
struct fenwick{
	int c[N];
	fenwick(){memset(c,0,sizeof(c));}
	inline void add(int x,int k,int n){while(x<=n) c[x]+=k,x+=lowbit(x);}
	inline int sum(int x){int res=0;while(x){res+=c[x],x-=lowbit(x);}return res;}
}BIT;
signed main(){
	n=read();
	for(int i=2;i<=n+1;++i) a[i]=read();
	for(int i=2;i<=n+1;++i){
		lst[i]=pos[a[i]]+1;
		pos[a[i]]=i;
	}
	m=read();
	for(int l,r,i=1;i<=m;++i){
		l=read()+1,r=read()+1;
		idzh[r]=i,zh[r]=l;
		if(l!=2)idfu[l-1]=i,fu[l-1]=l;
	}
	for(int i=2;i<=n+1;++i){
		BIT.add(lst[i],1,n+1);
		if(idfu[i])ans[idfu[i]]-=BIT.sum(fu[i]-1);
		if(idzh[i])ans[idzh[i]]+=BIT.sum(zh[i]-1);
	}
	for(int i=1;i<=m;++i) println(ans[i]);
	return 0;
}