#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 300100
#define M 2000100
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int kuailen;
inline int kuaiid(int x){
    return x/kuailen;
}

struct ques{
    int l,r,id,pos;
    inline bool operator < (const ques &b) const{
        return (pos^b.pos)?id<b.id:((pos&1)?r<b.r:r>b.r);
    }
};
int n,a[N],q;
ll ans[N],nowans,cnt[M];
ques b[M];

inline void add(int k){
    if(!cnt[a[k]]) nowans++;
    cnt[a[k]]++;
}

inline void del(int k){
    cnt[a[k]]--;
    if(!cnt[a[k]]) nowans--;
}

signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    read(q);
    kuailen=sqrt(n*n/q);
    for(int i=1;i<=q;i++){
        read(b[i].l);read(b[i].r);
        b[i].id=i;b[i].pos=b[i].id/kuailen;
    }
    sort(b+1,b+q+1);
    int r=0,l=1;
    for(int i=1;i<=q;i++){
        while(l>b[i].l) add(--l);
        while(r<b[i].r) add(++r);
        while(l<b[i].l) del(l++);
        while(r>b[i].r) del(r--);
        ans[b[i].id]=nowans;
    }
    for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;
};