#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]);
}