mO'S ALGO

#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define pb push_back
#define ff first
#define ss second
#define M 1000100
#define BLOCK 174

ll answer;

struct query
{
    ll  left,right,ind;
}Q[M+10];

ll ans[M+10];
ll ara[M+10];
ll mp[M+10];

void add(ll index)
{
    mp[ara[index]]++;
    if(mp[ara[index]]==1)
    {
        answer++;
       }
}

void _remove(int index)
{
    mp[ara[index]]--;
    if(mp[ara[index]]==0)
    {
        answer--;
     }

}

bool cmp(query f,query s)
{
    if((f.left/BLOCK)!=(s.left/BLOCK))
        return (f.left/BLOCK)<(s.left/BLOCK);
    else
        return f.right<s.right;
}

int main()
{
    ll n;

    cin>>n;

    for(ll i=0;i<n;i++)
    {
        cin>>ara[i];
    }

    ll q;


    cin>>q;

    for(ll i=0;i<q;i++)
    {
        ll a,b;

        cin>>a>>b;

        Q[i].ind=i;

        Q[i].left=a-1;

        Q[i].right=b-1;
    }

    sort(Q,Q+q,cmp);

    ll  cl=0,cr=0;

   for(ll i=0;i<q;i++)
    {
        ll left=Q[i].left,right=Q[i].right;

          while(cl<left)
        {
            _remove(cl),cl++;
        }
        while(cl>left)
        {
            add(cl-1),cl--;
        }
        while(cr<=right)
        {
            add(cr),cr++;
        }
        while(cr>(right+1))
        {
            _remove(cr-1),cr--;
        }

        ans[Q[i].ind]=answer;
    }
  for(ll i=0;i<q;i++)
  {
      cout<<ans[i]<<endl;
  }

  return 0;

}