#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void out(int x){ 
    if(x==0){putchar('0');return;}
	int len=0,k1=x,c[10005];
	if(k1<0)k1=-k1,putchar('-');
	while(k1)c[len++]=k1%10+'0',k1/=10;
	while(len--)putchar(c[len]);
}
const int N=1e6;
struct node{
    int L,R,k;
}q[N];
int pos[N],ans[N],cnt[N],a[N];
bool cmp(node a,node b){
    if(pos[a.L]!=pos[b.L])return pos[a.L]<pos[b.L];
    if(pos[a.L]&1)return a.R>b.R;
    return a.R<b.R;
}
int ANS=0;
void add(int x){
    cnt[a[x]]++;
    if(cnt[a[x]]==1)ANS++;
}
void del(int x){
    cnt[a[x]]--;
    if(cnt[a[x]]==0)ANS--;
}
int main(){
    int n=read();
    int block=sqrt(n);
    for(int i=1;i<=n;i++){
        a[i]=read();
        pos[i]=(i-1)/block+1;
    }
    int m=read();
    for(int i=1;i<=m;i++){
        q[i].L=read(),q[i].R=read();
        q[i].k=i;
    }
    sort(q+1,q+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;i++){
        while(L<q[i].L)del(L++);
        while(R>q[i].R)del(R--);
        while(L>q[i].L)add(--L);
        while(R<q[i].R)add(++R);
        ans[q[i].k]=ANS;
    }
    for(int i=1;i<=m;i++)out(ans[i]),puts("");
    return 0;
}