#pragma GCC optimize(2)
#include "bits/stdc++.h"
const int N = (int)1e6+10;
using namespace std;
struct query{
    int times,l,r;
}q[N];
int cnt[N],now;
int n,m,f[N],pos[N],ans[N];
bool cmp(query x,query y){
    if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l];
    else if(pos[x.l]&1)return pos[x.r]>pos[y.r];
    else return pos[x.r]<pos[y.r];
}
void build(){
    int len = (int)sqrt(n);
    for(int i=1;i<=n;i++){
        pos[i] = (i-1)/len + 1;
    }
}
inline void add(int x){
    if(!cnt[x])now++;
    cnt[x]++;
}
inline void del(int x){
    cnt[x]--;
    if(!cnt[x])now--;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&f[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        q[i] = {i,l,r};
    }
    build();
    sort(q+1,q+1+m,cmp);
    int l = 1,r = 0;
    for(int i=1;i<=m;i++){
        while(r<q[i].r)add(f[++r]);
        while(r>q[i].r)del(f[r--]);
        while(l<q[i].l)del(f[l++]);
        while(l>q[i].l)add(f[--l]);
        ans[q[i].times] = now;
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}