#include <stdio.h>
#include <math.h>

#include <algorithm>
#include <utility>

#define MAXN 100010
#define MAXM 100010

struct query {
  int first, second;
  int idx;
};

int A[MAXN];
query Q[MAXM];
int ans[MAXM];

int cnt[1000010];
int N, M;

int main( )
{
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }

  scanf("%d", &M);
  for (int i = 0; i < M; i++) {
    scanf("%d %d", &Q[i].first, &Q[i].second);
    Q[i].first--;
    Q[i].second--;
    Q[i].idx = i;
  }

  std::sort(Q, Q + M, [&](const query a, const query b) {
    const static int size = sqrt(N);
    return (a.second / size == b.second / size) ?  (a.first < b.first) :
      (a.second / size < b.second / size);
  });

  int l = Q[0].first, r = Q[0].first - 1;
  int count = 0;

  for (int i = 0; i < M; i++) {
    if (l < Q[i].first) {
      for (; l < Q[i].first; l++) {
        cnt[A[l]]--;
        if (cnt[A[l]] == 0) {
          count--;
        }
      }
    }
    else if (l > Q[i].first) {
      for (l = l - 1; l >= Q[i].first; l--) {
        if (cnt[A[l]] == 0) {
          count++;
        }
        cnt[A[r]]++;
      }
    }

    if (r < Q[i].second) {
      for (r = r + 1; r <= Q[i].second; r++) {
        if (cnt[A[r]] == 0) {
          count++;
        }
        cnt[A[r]]++;
      }
    }
    else if (r > Q[i].second) {
      for (; r >= Q[i].second + 1; r--) {
        cnt[A[r]]--;
        if (cnt[A[r]] == 0) {
          count--;
        }
      }
    }

    l = Q[i].first;
    r = Q[i].second;

    ans[Q[i].idx] = count;
  }

  for (int i = 0; i < M; i++) {
    printf("%d\n", ans[i]);
  }

  return 0;
}