#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, num, oks, sum[maxn], sq, ans[maxn], l, r, a[maxn], f[maxn], cnt[maxn];
vector<int> v[maxn];
vector<pair<pair<int, int>, int> > que;
deque<int> dq[maxn];
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
  if (a.first.first / sq == b.first.first / sq) {
    if ((a.first.first / sq) % 2 == 0) return a.first.second < b.first.second;
    return a.first.second > b.first.second;
  }
  return a.first.first < b.first.first;
}
bool isok(int x, int y) { return ((y - x == 2 && x % 2 == 0) || y - x <= 1); }
bool isart(int a, int b, int c) { return 2 * b == a + c; }
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i], v[a[i]].push_back(i);
  sq = sqrt(n);
  for (int i = 0; i < maxn; i++) {
    int tmp = 0;
    for (int j = 1; j < v[i].size(); j++)
      if (j != v[i].size() - 1 && !isart(v[i][j - 1], v[i][j], v[i][j + 1]))
        f[v[i][j]] = tmp + 2, tmp += 2;
      else
        f[v[i][j]] = tmp + 1;
  }
  cin >> m;
  for (int i = 0, fi, se; i < m; i++)
    cin >> fi >> se, fi--, que.push_back({{fi, se}, i});
  sort(que.begin(), que.end(), cmp);
  for (auto q : que) {
    int s = q.first.first, e = q.first.second;
    while (s < l) {
      l--;
      int cur = a[l];
      if (!cnt[cur]++) num++;
      if (dq[cur].size()) oks -= isok(dq[cur].back(), dq[cur].front());
      dq[cur].push_back(f[l]), oks += isok(dq[cur].back(), dq[cur].front());
    }
    while (r < e) {
      int cur = a[r];
      if (!cnt[cur]++) num++;
      if (dq[cur].size()) oks -= isok(dq[cur].back(), dq[cur].front());
      dq[cur].push_front(f[r]), oks += isok(dq[cur].back(), dq[cur].front());
      r++;
    }
    while (l < s) {
      int cur = a[l];
      cnt[cur]--;
      if (!cnt[cur]) num--;
      oks -= isok(dq[cur].back(), dq[cur].front());
      dq[cur].pop_back();
      if (dq[cur].size()) oks += isok(dq[cur].back(), dq[cur].front());
      l++;
    }
    while (e < r) {
      r--;
      int cur = a[r];
      cnt[cur]--;
      if (!cnt[cur]) num--;
      oks -= isok(dq[cur].back(), dq[cur].front());
      dq[cur].pop_front();
      if (dq[cur].size()) oks += isok(dq[cur].back(), dq[cur].front());
    }
    if (oks)
      ans[q.second] = num;
    else
      ans[q.second] = num + 1;
  }
  for (int i = 0; i < m; i++) cout << ans[i] << "\n";
}
