#include<bits/stdc++.h>
using namespace std;
void read(int& x) {
    x = 0;
    bool y = false;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        y = ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    if (y) x = -x;
}
const int N=1e6+10;
int n,m,a[N],b[N];
struct Tree{
	int l,r,data;
}tree[N<<5];
int root[N],ncnt;
void build_tree(int &u,int l,int r){
	u=++ncnt;
	if(l==r) return;
	int mid=(l+r)>>1;
	build_tree(tree[u].l,l,mid);
	build_tree(tree[u].r,mid+1,r);
}
void insert(int pre,int &u,int l,int r,int to){
	u=++ncnt;
	tree[u]=tree[pre];
	tree[u].data++;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(to<=mid) insert(tree[pre].l,tree[u].l,l,mid,to);
	else insert(tree[pre].r,tree[u].r,mid+1,r,to);
}
int ask(int pre,int u,int l,int r,int k){
	if(r<=k) return tree[u].data-tree[pre].data;
	int mid=(l+r)>>1;
	int dat=ask(tree[pre].l,tree[u].l,l,mid,k);
	if(mid<k) dat+=ask(tree[pre].r,tree[u].r,mid+1,r,k);
	return dat;
}
int main(){
	read(n);
	for(int i=1;i<=n;i++){
		int xx;
		read(xx);
		a[xx]=b[xx];
		b[xx]=i;
	}
	root[0]=0;
	for(int i=1;i<=n;i++){
		insert(root[i-1],root[i],0,n,a[i]);
	}
	read(m);
	for(int i=1;i<=m;i++){
		int L,R;
		read(L),read(R);
		int id=ask(root[L-1],root[R],0,n,L-1);
		printf("%d\n",id);
	}
	return 0;
}