#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;
typedef long long int LL;

struct node{
  int l;
  int r;
  int id;
}u[311111];

int z;
bool cool(node a,node b)
{
     if(a.l/z<b.l/z)
        return true;
     if(a.l/z>b.l/z)
        return false;
     return a.r<b.r;
}
 int cnt[1111111];
 int ans[311111];
 int v[311111];

int main()
{

     //ios_base:: sync_with_stdio(false); cin.tie(0);
      
   
    // freopen("input.in","r",stdin);
        
        int n;cin>>n;
        int fuk=0;
        z=sqrt(n);
      //  vector<int>v(n);
        
        for(int i=0;i<n;i++)
                scanf("%d",&v[i]);
                    
        int q;cin>>q;for(int i=0;i<q;i++)
        {
             int l,r;
             scanf("%d %d",&l,&r);
             node tmp;
             tmp.l=l-1;
             tmp.r=r-1;
             tmp.id=i;
             u[i]=tmp;
        }

         sort(u,u+q,cool);

         int st=0,e=0;fuk=1;cnt[v[0]]++;

        for(int i=0;i<q;i++)
        {
            int l=u[i].l;
            int r=u[i].r;
           // cout<<l<<" "<<r<<" "<<st<<" "<<e<<" "<<fuk<<endl;
            
            while(st<l)
            {
                cnt[v[st]]--;
                if(cnt[v[st]]==0)
                 fuk--;
                 st++;
            }
            while(st>l)
            {
                 st--;
                 cnt[v[st]]++;
                 if(cnt[v[st]]==1)
                 fuk++;
            }
            while(e<r)
            {
                e++;
                cnt[v[e]]++;
                if(cnt[v[e]]==1)
                fuk++;
            }
            while(e>r)
            {
               cnt[v[e]]--;
               if(cnt[v[e]]==0)
               fuk--;
               e--;
            }            
            ans[u[i].id]=fuk;
        }

        for(int i=0;i<q;i++)
            printf("%d\n",ans[i]);

     return 0;
}