#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
int n,m,A[N],book[N],ID[N],ans[N];
//book记录是否已经插入线段树
//ID记录上次插入的数所在位置 
struct node{
	int l,r,val,lazy;
};
node T[N << 2];
struct node2{
	int L,R,id;
};
node2 B[N];
bool cmp(node2 a,node2 b){
	if(a.R != b.R) return a.R < b.R;
	else return a.id < b.id; 
}
inline void read(int &x){
	char ch = getchar();int f = 1;x = 0;
	while(!isdigit(ch) && ch ^ '-') ch = getchar();
	if(ch == '-') f = -1,ch = getchar();
	while(isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
	x *= f;
}
void build(int l,int r,int i){
	int t1,t2,k;
	t1 = i << 1;t2 = i << 1 | 1;
	T[i].l = l;T[i].r = r;
	if(l == r) return;
	k = (l + r) >> 1;
	build(l,k,t1);
	build(k + 1,r,t2);
}
void update(int i,int l,int r,int k){
	int t1,t2;
	t1 = i << 1;t2 = i << 1 | 1;
	if(T[i].l == l && T[i].r == r){
		T[i].val = k;
		return;
	}
	if(T[t1].r >= r) update(t1,l,r,k);
	else if(T[t2].l <= l) update(t2,l,r,k);
	else{
		update(t1,l,T[t1].r,k);
		update(t2,T[t2].l,r,k);
	}
	T[i].val = T[t1].val + T[t2].val;
}
int query(int l,int r,int i){
	int t1,t2;
	t1 = i << 1;t2 = i << 1 | 1;
	if(T[i].l == l && T[i].r == r) return T[i].val;
	if(T[t1].r >= r) return query(l,r,t1);
	else if(T[t2].l <= l) return query(l,r,t2);
	else return query(l,T[t1].r,t1) + query(T[t2].l,r,t2);
}
int main(){
	int i,j,k = 1,x,y;
	read(n);
	for(i = 1;i <= n;i++) read(A[i]);
	build(1,n,1);
	read(m);
	for(i = 1;i <= m;i++){
		read(B[i].L);
		read(B[i].R);
		B[i].id = i;
	}
	sort(B + 1,B + 1 + m,cmp);
//	for(i = 1;i <= m;i++){
//		cout<<B[i].L <<' '<<B[i].R<<' '<<B[i].id<<endl;
//	}
	for(i = 1;i <= m;i++){
		for(j = B[i].L;j <= B[i].R;j++){
//			cout<<book[A[j]]<<' ';
			if(book[A[j]] == 0){
				book[A[j]] = 1;
				ID[A[j]] = j; 
				update(1,j,j,1);
			}
			else{
				if(ID[A[j]] == j) continue;
				update(1,ID[A[j]],ID[A[j]],0);
				ID[A[j]] = j;
				update(1,j,j,1);
 			}
		} 
//		cout<<endl;
		ans[B[i].id] = query(B[i].L,B[i].R,1);
	}
//	cout<<endl<<endl;
	for(i = 1;i <= m;i++) printf("%d\n",ans[i]);
}