#include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 int id[maxn],tree[maxn],vis[maxn],num[maxn];

 int n,m;

 struct Tree{

     int l,r;

     int pos;

 };

 Tree a[maxn];

 int buf[];

 inline void read(int &x){

     char ch=getchar(); x=;

     while(ch<'') ch=getchar();

     while(ch>='' && ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();

 }

 inline void write(int x){

     if(!x){putchar('');putchar(' ');return;}

     register int cnt=;

     while(x)buf[++cnt]=(x%)+,x/=;

     while(cnt)putchar(buf[cnt--]);

     putchar('\n');

 }

 bool cmp(Tree x,Tree y){

     return x.r < y.r;

 }

 int lowbit(int x){

     return x & -x;

 }

 void add(int x,int now){

     while(x <= n){

         tree[x] += now;

         x += lowbit(x);

     }

 }

 int sum(int n){

     int ans = ;

     while(n != ){

         ans += tree[n];

         n -= lowbit(n);

     }

     return ans;

 }

 int main(){

     read(n);

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

         read(id[i]);

     read(m);

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

         read(a[i].l);

         read(a[i].r);

         a[i].pos = i;

     }

     sort(a+,a++m,cmp);

     int next = ;

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

         for(int j = next;j <= a[i].r;j++){

             if(vis[id[j]])

                 add(vis[id[j]],-);

             add(j,);

             vis[id[j]] = j;

         }

         next = a[i].r+;

         num[a[i].pos] = sum(a[i].r)-sum(a[i].l-);

     }

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

         write(num[i]);

     return  ;

 }

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = 5e6+;

 struct segment_tree{

     int l,r,s,sum;

 };

 segment_tree ask[maxn<<],tree[maxn<<];

 int next[maxn],pre[maxn],a[maxn],x[maxn],n,m;

 int buf[];

 inline void read(int &x){

     char ch=getchar(); x=;

     while(ch<'') ch=getchar();

     while(ch>='' && ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();

 }

 inline void write(int x){

     if(!x){putchar('');putchar(' ');return;}

     register int cnt=;

     while(x)buf[++cnt]=(x%)+,x/=;

     while(cnt)putchar(buf[cnt--]);

     putchar('\n');

 }

 bool cmp1(segment_tree x,segment_tree y){

     if (x.l == y.l)return x.r < y.r;

     else return x.l < y.l;

 }

 bool cmp2(segment_tree x,segment_tree y){

     return x.s < y.s;

 }

 inline void pushup(int root){

     tree[root].sum = tree[root<<].sum+tree[root<<|].sum;

 }

 inline void build(int root,int l,int r){

     tree[root].l = l;

     tree[root].r = r;

     if(l == r){

         tree[root].sum = a[l];

         return;

     }

     int mid = (l+r)>>;

     build(root<<,l,mid);

     build(root<<|,mid+,r);

     pushup(root);

 }

 inline void update(int root,int k){

     if (tree[root].l == k && tree[root].r == k){

         a[k] = ;

         tree[root].sum = a[k];

         return;

     }

     int mid = (tree[root].l+tree[root].r)>>;

     if(k <= mid)update(root<<,k);

     else update(root<<|,k);

     pushup(root);

 }

 inline int query(int root,int l,int r){

     if(tree[root].l == l && tree[root].r == r)

         return tree[root].sum;

     int mid = (tree[root].l+tree[root].r)>>;

     if(r <= mid)return query(root<<,l,r);

     else

         if(l > mid)return query(root<<|,l,r);

         else return(query(root<<,l,mid)+query(root<<|,mid+,r));

 }

 int main(){

     read(n);

     for(register int i = ;i <= n;i++){

         read(x[i]);

         next[pre[x[i]]] = i;

         if(!pre[x[i]])a[i] = ;

         pre[x[i]] = i;

     }

     build(,,n);

     scanf("%d",&m);

     for(register int i = ;i <= m;i++){

         read(ask[i].l);

         read(ask[i].r);

         ask[i].s = i;

     }

     sort(ask+,ask+m+,cmp1);

     ask[].l = ;

     for(register int i = ;i <= m;i++){

         if(ask[i-].l != ask[i].l)

             for(register int j = ask[i-].l;j <= ask[i].l-;j++)

                 if(next[j])update(,next[j]);

         ask[i].sum = query(,ask[i].l,ask[i].r);

     }

     sort(ask+,ask+m+,cmp2);

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

         write(ask[i].sum);

     return ;

 }