#include <bits/stdc++.h>
 
using namespace std;
 
int const N = 1 << 15;
int const M = 1 << 18;
 
int n, m;
int a[N];
 
pair<int, pair<int, int>> q[M];
 
bool sort_queries(pair<int, pair<int, int>> const& a, pair<int, pair<int, int>> const& b) {
  return a.second.second < b.second.second;
}
 
int bit[N];
 
void update(int idx, int v) {
  while(idx < N)
    bit[idx] += v, idx += (idx&-idx);
}
 
int query(int idx) {
  int sum = 0;
  while(idx > 0)
    sum += bit[idx], idx -= (idx&-idx);
  return sum;
}
 
int ans[M];
 
int main() {
  scanf("%d",&n);
  for(int i = 1; i <= n; ++i)
    scanf("%d",a+i);
 
  scanf("%d",&m);
  for(int i = 0; i < m; ++i)
    scanf("%d%d",&q[i].second.first,&q[i].second.second), q[i].first = i;
 
  sort(q,q+m,sort_queries);
 
  map<int,int> last;
 
  int R = 1;
  for(int i = 0; i < m; ++i) {
    int idx = q[i].first;
    int l = q[i].second.first;
    int r = q[i].second.second;
 
    while(R <= r) {
      int x = a[R];
 
      auto f = last.find(x);
 
      if(f == last.end())
        last[x] = R;
      else
        update(f->second, -1), f->second = R;
 
      update(R++, 1);
    }
 
    ans[idx] = query(r) - query(l-1);
  }
 
  for(int i = 0; i < m; ++i)
    printf("%d\n", ans[i]);
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGNvbnN0IE4gPSAxIDw8IDE1OwppbnQgY29uc3QgTSA9IDEgPDwgMTg7CgppbnQgbiwgbTsKaW50IGFbTl07CgpwYWlyPGludCwgcGFpcjxpbnQsIGludD4+IHFbTV07Cgpib29sIHNvcnRfcXVlcmllcyhwYWlyPGludCwgcGFpcjxpbnQsIGludD4+IGNvbnN0JiBhLCBwYWlyPGludCwgcGFpcjxpbnQsIGludD4+IGNvbnN0JiBiKSB7CiAgcmV0dXJuIGEuc2Vjb25kLnNlY29uZCA8IGIuc2Vjb25kLnNlY29uZDsKfQoKaW50IGJpdFtOXTsKCnZvaWQgdXBkYXRlKGludCBpZHgsIGludCB2KSB7CiAgd2hpbGUoaWR4IDwgTikKICAgIGJpdFtpZHhdICs9IHYsIGlkeCArPSAoaWR4Ji1pZHgpOwp9CgppbnQgcXVlcnkoaW50IGlkeCkgewogIGludCBzdW0gPSAwOwogIHdoaWxlKGlkeCA+IDApCiAgICBzdW0gKz0gYml0W2lkeF0sIGlkeCAtPSAoaWR4Ji1pZHgpOwogIHJldHVybiBzdW07Cn0KCmludCBhbnNbTV07CgppbnQgbWFpbigpIHsKICBzY2FuZigiJWQiLCZuKTsKICBmb3IoaW50IGkgPSAxOyBpIDw9IG47ICsraSkKICAgIHNjYW5mKCIlZCIsYStpKTsKCiAgc2NhbmYoIiVkIiwmbSk7CiAgZm9yKGludCBpID0gMDsgaSA8IG07ICsraSkKICAgIHNjYW5mKCIlZCVkIiwmcVtpXS5zZWNvbmQuZmlyc3QsJnFbaV0uc2Vjb25kLnNlY29uZCksIHFbaV0uZmlyc3QgPSBpOwoKICBzb3J0KHEscSttLHNvcnRfcXVlcmllcyk7CgogIG1hcDxpbnQsaW50PiBsYXN0OwoKICBpbnQgUiA9IDE7CiAgZm9yKGludCBpID0gMDsgaSA8IG07ICsraSkgewogICAgaW50IGlkeCA9IHFbaV0uZmlyc3Q7CiAgICBpbnQgbCA9IHFbaV0uc2Vjb25kLmZpcnN0OwogICAgaW50IHIgPSBxW2ldLnNlY29uZC5zZWNvbmQ7CgogICAgd2hpbGUoUiA8PSByKSB7CiAgICAgIGludCB4ID0gYVtSXTsKCiAgICAgIGF1dG8gZiA9IGxhc3QuZmluZCh4KTsKCiAgICAgIGlmKGYgPT0gbGFzdC5lbmQoKSkKICAgICAgICBsYXN0W3hdID0gUjsKICAgICAgZWxzZQogICAgICAgIHVwZGF0ZShmLT5zZWNvbmQsIC0xKSwgZi0+c2Vjb25kID0gUjsKCiAgICAgIHVwZGF0ZShSKyssIDEpOwogICAgfQoKICAgIGFuc1tpZHhdID0gcXVlcnkocikgLSBxdWVyeShsLTEpOwogIH0KCiAgZm9yKGludCBpID0gMDsgaSA8IG07ICsraSkKICAgIHByaW50ZigiJWRcbiIsIGFuc1tpXSk7Cn0=

NQoxIDEgMiAxIDMKMwoxIDUKMiA0CjMgNQ==

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