#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cmath>

using namespace std;

#define N 50005

#define M 1000005

int n,m,a[N],last[M];

struct node

{

    int l,r,ans,idx;

}q[N<<2];

bool cmp(const node &c,const node &b){return c.r<b.r;}

bool cmp1(const node &a,const node &b){return a.idx<b.idx;}

int sum[N];

void fix(int x,int c){for(int i=x;i<=n;i+=i&-i)sum[i]+=c;}

int find(int x)

{

    int ret=0;

    for(int i=x;i;i-=i&-i)ret+=sum[i];

    return ret;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    scanf("%d",&m);

    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].idx=i;

    sort(q+1,q+m+1,cmp);

    int cnt=1;

    for(int i=1;i<=n;i++)

    {

        if(last[a[i]])fix(last[a[i]],-1);

        fix(i,1);

        last[a[i]]=i;

        while(q[cnt].r==i)q[cnt].ans=find(i)-find(q[cnt].l-1),cnt++;

    }

    sort(q+1,q+m+1,cmp1);

    for(int i=1;i<=m;i++)

    {

        printf("%d\n",q[i].ans);

    }

    return 0;

}