#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
using TPL = pair<PII, int>;
class BITree {
 public:
  static const int SIZE = 100010, 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;
  }
} s, g;
int o[100005];
int v[100005], gap[100005];
int a[100005], ans[100005];
TPL u[100005];
int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    u[i] = {{y - 1, x - 1}, i};
  }
  sort(u, u + m);
  u[m] = {{n, n}, m};
  memset(v, -1, sizeof(v));
  memset(o, -1, sizeof(o));
  for (int i = 0, j = 0; i < n; i++) {
    if (~v[a[i]]) {
      s.modify(v[a[i]], -1);
      gap[i] = i - v[a[i]];
      if (gap[i] != gap[v[a[i]]] && gap[v[a[i]]]) {
        if (~o[a[i]]) g.modify(o[a[i]], -1);
        g.modify(o[a[i]] = v[a[i]] - gap[v[a[i]]], 1);
      }
    }
    s.modify(v[a[i]] = i, 1);
    while (i == u[j].first.first) {
      int cnt = s.getsum(i) - s.getsum(u[j].first.second - 1);
      int tag = g.getsum(i) - g.getsum(u[j].first.second - 1);
      ans[u[j++].second] = cnt + (tag == cnt);
    }
  }
  for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
}
