#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
class BITree {
 public:
  static const int SIZE = 1e5 + 7, BIAS = 5;
  int u[SIZE];
  void modify(int x, int v) {
    for (x += BIAS; x < SIZE; x += x & -x) u[x] += v;
  }
  int getsum(int x) {
    int s = 0;
    for (x += BIAS; x; x -= x & -x) s += u[x];
    return s;
  }
} c, g;
int n, m, a[MAXN];
tuple<int, int, int> q[MAXN];
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    q[i] = tuple<int, int, int>(r, l, i);
  }
  sort(q, q + m);
  q[m] = tuple<int, int, int>(n, n, m);
}
int p[MAXN], gap[MAXN], l[MAXN];
int ans[MAXN];
void solve() {
  for (int i = 1, j = 0; i <= n; i++) {
    if (p[a[i]]) {
      c.modify(p[a[i]], -1);
      gap[i] = i - p[a[i]];
      if (gap[i] != gap[p[a[i]]] && gap[p[a[i]]]) {
        if (l[a[i]]) g.modify(l[a[i]], -1);
        int pre = p[a[i]] - gap[p[a[i]]];
        g.modify(l[a[i]] = pre, 1);
      }
    }
    c.modify(p[a[i]] = i, 1);
    while (i == get<0>(q[j])) {
      int tot = c.getsum(i) - c.getsum(get<1>(q[j]) - 1);
      int dif = g.getsum(i) - g.getsum(get<1>(q[j]) - 1);
      ans[get<2>(q[j++])] = tot + (tot == dif);
    }
  }
  for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
}
int main() {
  init();
  solve();
  return 0;
}
