MO's

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 3e4 + 5;
const int Q = 2e5 + 1;
const int mod = 1e9 + 7;

ll bsize , a[N],cnt,ans[Q];
ll q , n;
ll mp[1000001];
struct node{

   int l , r , idx;
};
node query[Q];
void init(){
   for(int i = 0 ; i < q ; i++ ){
      ll l , r;
      cin >> l >> r ;
      query[i].l = l;
      query[i].r = r;
      query[i].idx = i;
    }
}
bool cmp(node q1 , node q2){
   if(q1.l/bsize == q2.l/bsize)return q1.r < q2.r;
   return q1.l < q2.l;
}
/*bool cmp(node q1, node q2)
{
    int l1 = q1.l / n;
    int l2 = q2.l / n;
    if(l1 == l2)
    return q1.r < q2.r;
    else return l1 < l2;
}
*/
void add(ll val){
   mp[val]++;
   if(mp[val] == 1)
      cnt++;
}
void remove(ll val){
   mp[val]--;
   if(mp[val] == 0)
      cnt--;
}
void Query(){
    ll lcurr  = 1 , rcurr =  0;
    for(int i = 0 ; i < q; i++ ){
      ll l = query[i].l;
      ll r = query[i].r;
      while(l < lcurr){
         lcurr--;
         add(a[lcurr]);
      }
      while(r > rcurr){
         rcurr++;
         add(a[rcurr]);
      }
      while(l > lcurr){
         remove(a[lcurr]);
         lcurr++;
      }
      while(r < rcurr){
         remove(a[rcurr]);
         rcurr--;
      }

      ans[query[i].idx] = cnt;
    }
}

int main()
{
    fast;

    cin >> n ;
    bsize = sqrt(n);

    for(int i = 1 ;  i <= n; i++ ){
      cin >> a[i];
    }
    cin >> q;
    init();

    sort(query   , query + q,cmp);
   Query();
    for(int i = 0 ;  i < q ; i++ )
      cout << ans[i] << "\n";
























    return 0;

}