#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Inline __inline__ __attribute__((always_inline))
template<typename T>
Inline void read(T &x){ x=0;register int f=1;register char c=getchar();while(c < '0' || c > '9'){if(c=='-')f=-1;c=getchar();}while(c >= '0' && c <= '9'){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
Inline void read(T &x, Args &... y){ read(x);read(y...); }
int a[1000005],tong[1000005],n,m,s,l,r,t,num;
struct node {int l1,l,r,i,ans;} z[1000005];
bool cmp(node o,node p){return o.l1==p.l1?(o.l1&1)?o.r<p.r:o.r>p.r:o.l1<p.l1;}
void add(int x) {if (tong[a[x]]++==0) num++;}
void del(int x) {if (tong[a[x]]--==1) num--;}
bool cmp2(node a,node b) {return a.i<b.i;}
signed main(){
    read(n);
    for (int i=1;i<=n;i++) read(a[i]);
    read(m),s=sqrt(n);
    for (int i=1;i<=m;i++) read(z[i].l,z[i].r),z[i].l1=z[i].l/s,z[i].i=i;
    sort(z+1,z+m+1,cmp);
    int l=0,r=0;
    for (int i=1;i<=m;i++){
        while (r<z[i].r) add(++r);
        while (r>z[i].r) del(r--);
        while (l>z[i].l) add(--l);
        while (l<z[i].l) del(l++);
        z[i].ans=num;
    }
    sort(z+1,z+m+1,cmp2);
    for (int i=1;i<=m;i++) printf("%lld\n",z[i].ans);
    return 0;
}

36pts