/*
Language: c++
Author: lxtgogogo
Date: 2016.04.07
暴力大法好
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
using namespace std;
inline int read(){
	int x=0;bool f=true;char ch=getchar();
	while(ch>'9' || ch<'0')	{if(ch=='-'){f=false;}ch=getchar();}
	while(ch>='0' && ch<='9')	{x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f?x:-x;
}
const int r=50010;
const int rr=200010;
const int num=1000010;
int n=0,m=0,maxx;
int a[r]={},live[num]={},nex[r]={};
bool f[r]={};
int treenum[r]={};

struct hehe{
	int x,y,id,ans;
}ask[rr];

bool mycmp1(hehe a,hehe b){return a.x<b.x;}
bool mycmp2(hehe a,hehe b){return a.id<b.id;}
void add(int k,int x){
	while(k<r){treenum[k]+=x;k+=k&(-k);}
}
int find(int k){
	int t=0;
	while(k>0){t+=treenum[k];k-=k&(-k);}
	return t;
}
void init(){
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		maxx=max(maxx,a[i]);
	}
	m=read();
	for(int i=1;i<=m;i++)	{ask[i].x=read();ask[i].y=read();ask[i].id=i;}
	sort(ask+1,ask+m+1,mycmp1);
}
void work(){
	for(int i=n;i>=1;i--){nex[i]=live[a[i]];live[a[i]]=i;}
	for(int i=1;i<=maxx;i++)
		if(live[i]!=0)	{add(live[i],1);f[live[i]]=true;}
	int i=1;
	for(int j=1;j<=m;j++)
	{
		while(i<ask[j].x)
		{
			if(f[i])
			{
				add(i,-1);
				if(nex[i]!=0)	{add(nex[i],1);f[nex[i]]=true;}
			}
			i++;
		}
		ask[j].ans=find(ask[j].y);
	}
	sort(ask+1,ask+m+1,mycmp2);
	for(int i=1;i<=m;i++)
		printf("%d\n",ask[i].ans);
}
int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	
	init();
	work();
	
	fclose(stdin);fclose(stdout);
	return 0;
}