#include <bits/stdc++.h>

using namespace std;

int const N = 30 * 1000 + 16;

int n, m;
int a[N], b[N], last[N];

struct tree {
  int v;
  tree *lf, *rg;
  
  tree(tree* tmp) {
    *this = *tmp;
  }
  
  tree(int l, int r) {
    v = 0;
    if(l == r)
      return;
    int m = l + r >> 1;
    lf = new tree(l, m);
    rg = new tree(m+1, r);
  }
  
  int query(int l, int r, int L, int R) {
    if(L <= l && r <= R)
      return v;
    int m = l + r >> 1;
    if(R <= m)
      return lf->query(l, m, L, R);
    else if(m < L)
      return rg->query(m+1, r, L, R);
    else
      return lf->query(l, m, L, m) + rg->query(m+1, r, m+1, R);
  }
  
  tree* update(int l, int r, int i, int v) {
    auto tmp = new tree(this);
    if(l == i && i == r) {
      tmp->v = v;
    } else {
      int m = l+r>>1;
      if(i <= m)
        tmp->lf = lf->update(l, m, i, v);
      else
        tmp->rg = rg->update(m+1, r, i, v);
      tmp->v = tmp->lf->v + tmp->rg->v;
    }    
    return tmp;
  }
};

tree* ver[N];

int main()
{
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    a[i] = b[i-1] = x;
  }
  sort(b, b+n);
  m = unique(b, b+n) - b;
  
  ver[0] = new tree(1, n);
  
  for(int i = 1; i <= n; ++i) {
    int x = lower_bound(b, b+m, a[i]) - b;
    auto old = ver[i-1];
    if(last[x])
      old = old->update(1, n, last[x], 0);
    ver[i] = old->update(1, n, i, 1);
    last[x] = i;
  }
  
  int q;
  scanf("%d", &q);
  while(q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", ver[r]->query(1, n, l, r));
  }
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGNvbnN0IE4gPSAzMCAqIDEwMDAgKyAxNjsKCmludCBuLCBtOwppbnQgYVtOXSwgYltOXSwgbGFzdFtOXTsKCnN0cnVjdCB0cmVlIHsKICBpbnQgdjsKICB0cmVlICpsZiwgKnJnOwogIAogIHRyZWUodHJlZSogdG1wKSB7CiAgICAqdGhpcyA9ICp0bXA7CiAgfQogIAogIHRyZWUoaW50IGwsIGludCByKSB7CiAgICB2ID0gMDsKICAgIGlmKGwgPT0gcikKICAgICAgcmV0dXJuOwogICAgaW50IG0gPSBsICsgciA+PiAxOwogICAgbGYgPSBuZXcgdHJlZShsLCBtKTsKICAgIHJnID0gbmV3IHRyZWUobSsxLCByKTsKICB9CiAgCiAgaW50IHF1ZXJ5KGludCBsLCBpbnQgciwgaW50IEwsIGludCBSKSB7CiAgICBpZihMIDw9IGwgJiYgciA8PSBSKQogICAgICByZXR1cm4gdjsKICAgIGludCBtID0gbCArIHIgPj4gMTsKICAgIGlmKFIgPD0gbSkKICAgICAgcmV0dXJuIGxmLT5xdWVyeShsLCBtLCBMLCBSKTsKICAgIGVsc2UgaWYobSA8IEwpCiAgICAgIHJldHVybiByZy0+cXVlcnkobSsxLCByLCBMLCBSKTsKICAgIGVsc2UKICAgICAgcmV0dXJuIGxmLT5xdWVyeShsLCBtLCBMLCBtKSArIHJnLT5xdWVyeShtKzEsIHIsIG0rMSwgUik7CiAgfQogIAogIHRyZWUqIHVwZGF0ZShpbnQgbCwgaW50IHIsIGludCBpLCBpbnQgdikgewogICAgYXV0byB0bXAgPSBuZXcgdHJlZSh0aGlzKTsKICAgIGlmKGwgPT0gaSAmJiBpID09IHIpIHsKICAgICAgdG1wLT52ID0gdjsKICAgIH0gZWxzZSB7CiAgICAgIGludCBtID0gbCtyPj4xOwogICAgICBpZihpIDw9IG0pCiAgICAgICAgdG1wLT5sZiA9IGxmLT51cGRhdGUobCwgbSwgaSwgdik7CiAgICAgIGVsc2UKICAgICAgICB0bXAtPnJnID0gcmctPnVwZGF0ZShtKzEsIHIsIGksIHYpOwogICAgICB0bXAtPnYgPSB0bXAtPmxmLT52ICsgdG1wLT5yZy0+djsKICAgIH0gICAgCiAgICByZXR1cm4gdG1wOwogIH0KfTsKCnRyZWUqIHZlcltOXTsKCmludCBtYWluKCkKewogIHNjYW5mKCIlZCIsICZuKTsKICBmb3IoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgewogICAgaW50IHg7CiAgICBzY2FuZigiJWQiLCAmeCk7CiAgICBhW2ldID0gYltpLTFdID0geDsKICB9CiAgc29ydChiLCBiK24pOwogIG0gPSB1bmlxdWUoYiwgYituKSAtIGI7CiAgCiAgdmVyWzBdID0gbmV3IHRyZWUoMSwgbik7CiAgCiAgZm9yKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgIGludCB4ID0gbG93ZXJfYm91bmQoYiwgYittLCBhW2ldKSAtIGI7CiAgICBhdXRvIG9sZCA9IHZlcltpLTFdOwogICAgaWYobGFzdFt4XSkKICAgICAgb2xkID0gb2xkLT51cGRhdGUoMSwgbiwgbGFzdFt4XSwgMCk7CiAgICB2ZXJbaV0gPSBvbGQtPnVwZGF0ZSgxLCBuLCBpLCAxKTsKICAgIGxhc3RbeF0gPSBpOwogIH0KICAKICBpbnQgcTsKICBzY2FuZigiJWQiLCAmcSk7CiAgd2hpbGUocS0tKSB7CiAgICBpbnQgbCwgcjsKICAgIHNjYW5mKCIlZCVkIiwgJmwsICZyKTsKICAgIHByaW50ZigiJWRcbiIsIHZlcltyXS0+cXVlcnkoMSwgbiwgbCwgcikpOwogIH0KfQ==

NQoxIDEgMiAxIDMKMwoxIDUKMiA0CjMgNQ==

5
1 1 2 1 3
3
1 5
2 4
3 5