#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 1e6 + 100;

int n, m, lr = n, a[N], la[N], nx[N], c[N], ans[N];

struct Q {
  int l, r, i;
} q[N];

int lb(int x) {
  return x & -x;
}

void upd(int x, int k) {
  for (int i = x; i <= n; i += lb(i)) {
    c[i] += k;
  }
}

int qry(int x) {
  int res = 0;
  for (int i = x; i; i -= lb(i)) {
    res += c[i];
  }
  return res;
}

signed main() {
  freopen("P1972_5.in", "r", stdin);
  read(n);
  For(i,1,n) {
    read(a[i]);
    if(la[a[i]]) nx[i] = la[a[i]], upd(nx[i], -1), upd(i, 1);
    else upd(i, 1);
    la[a[i]] = i;
  }
  read(m);
  For(i,1,m) read(q[i].l, q[i].r), q[i].i = i;
  sort(q + 1, q + m + 1, [](Q x, Q y){return (x.r == y.r ? x.l > y.l : x.r > y.r);});
  For(i,1,m) {
    int l = q[i].l, r = q[i].r;
//    cout << "---start---\n";
//    cout << l << ' ' << r << '\n';
//    cout << "---end---\n";
    if(lr != r) {
      FOR(j,lr,r+1) {
        if(nx[j]) {
          upd(nx[j], 1); upd(j, -1);
        } else {
          upd(j, -1);
        }
      }  
    }
    ans[q[i].i] = qry(r) - qry(l-1);
    lr = r;
  }
  For(i,1,m) if(i == 97) cout << ans[i] << '\n';
  return 0;
}

Wa的点的询问都刚刚好少$1$。