#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;

int n,m;
int num[N],cnt[1000007],out[N*4];

struct Query{
    int l,r;
    int id;
}q[N*4];

int len;

bool cmp(Query x,Query y){
    if(x.l/len==y.l/len){
        if(x.l/len%2){
            return x.r<y.r;
        }
        return x.r>y.r;
    }
    else{
        return x.l<y.l;
    }
}

void read(int &x){
	char ch=getchar();int f=1;x=0;
	while(!isdigit(ch) && ch^'-') ch=getchar();
	if(ch=='-') f=-1,ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}

int main()
{
    read(n);
    for(int i=1;i<=n;i++){
        read(num[i]);
    }
    read(m);
    len=n/sqrt(m);
    for(int i=0;i<m;i++){
        read(q[i].l);
        read(q[i].r);
        q[i].id=i;
    }
    sort(q,q+m,cmp);
    int ll=1,rr=1;
    int ans=1;
    cnt[num[ll]]++;
    for(int i=0;i<m;i++){
        while(rr<q[i].r){
            rr++;
            cnt[num[rr]]++;
            if(cnt[num[rr]]==1){
                ans++;
            }
        }
        while(rr>q[i].r){
            cnt[num[rr]]--;
            if(cnt[num[rr]]==0){
                ans--;
            }
            rr--;
        }
        while(ll>q[i].l){
            ll--;
            cnt[num[ll]]++;
            if(cnt[num[ll]]==1){
                ans++;
            }
        }
        while(ll<q[i].l){
            cnt[num[ll]]--;
            if(cnt[num[ll]]==0){
                ans--;
            }
            ll++;
        }
        out[q[i].id]=ans;
    }
    for(int i=0;i<m;i++){
        cout<<out[i]<<endl;
    }
    return 0;
}