Cosider a sequence, consisting of n integers: a1, a2, ..., an. Jeff can perform the following operation on sequence a:

  * take three integers v, t, k (1 ≤ v, t ≤ n; 0 ≤ k; v + tk ≤ n), such that av = av + t, av + t = av + 2t, ..., av + t(k - 1) = av + tk; 
  * remove elements av, av + t, ..., av + t·k from the sequence a, the remaining elements should be reindexed a1, a2, ..., an - k - 1. 
  * permute in some order the remaining elements of sequence a. 



A beauty of a sequence a is the minimum number of operations that is needed to delete all elements from sequence a.

Jeff's written down a sequence of m integers b1, b2, ..., bm. Now he wants to ask q questions. Each question can be described with two integers li, ri. The answer to the question is the beauty of sequence bli, bli + 1, ..., bri. You are given the sequence b and all questions. Help Jeff, answer all his questions.

Input

The first line contains integer m (1 ≤ m ≤ 105). The next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 105). 

The third line contains integer q (1 ≤ q ≤ 105) — the number of questions. The next q lines contain pairs of integers, i-th of them contains a pair of integers li, ri (1 ≤ li ≤ ri ≤ m) — the description of i-th question.

Output

In q lines print the answers to Jeff's queries. Print the answers according to the order of questions in input.

Examples

Input

5
2 2 1 1 2
5
1 5
1 1
2 2
1 3
2 3


Output

2
1
1
2
2


Input

10
2 1 3 3 3 3 1 3 1 1
10
4 8
2 10
1 10
4 4
1 3
2 4
6 7
1 9
2 5
1 1


Output

2
3
3
1
3
2
2
3
2
1
#include <bits/stdc++.h>
const int ms = 200100;
int n;
int tree[ms];
void build() { memset(tree, -1, sizeof tree); }
void upd(int pos, int val) {
  pos += n;
  tree[pos] = val;
  while (pos > 1) {
    pos /= 2;
    tree[pos] = std::max(tree[pos + pos], tree[pos + pos + 1]);
  }
}
int qry(int l, int r) {
  int ans = -1;
  for (l += n, r += n; l < r; l /= 2, r /= 2) {
    if (l & 1) ans = std::max(ans, tree[l++]);
    if (r & 1) ans = std::max(ans, tree[--r]);
  }
  return ans;
}
int a[ms];
struct Info {
  int l, r, idx;
  void read(int i) {
    idx = i;
    std::cin >> l >> r;
    l--;
    r--;
  }
};
struct BIT {
  int a[ms];
  void init() { memset(a, 0, sizeof a); }
  int qry(int x) {
    x++;
    int ans = 0;
    for (; x > 0; x -= x & -x) ans += a[x];
    return ans;
  }
  void upd(int x, int v) {
    x++;
    for (; x < ms; x += x & -x) a[x] += v;
  }
};
BIT wtf;
bool operator<(Info a, Info b) { return a.l < b.l; }
Info qries[ms];
std::vector<int> pos[ms];
int where[ms];
int ans[ms], to[ms];
int main() {
  std::cin >> n;
  wtf.init();
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    pos[a[i]].push_back(i);
  }
  build();
  int m;
  std::cin >> m;
  for (int i = 0; i < m; i++) {
    qries[i].read(i);
  }
  for (int i = 0; i < ms; i++) {
    if (pos[i].empty()) continue;
    for (int j = pos[i].size() - 1; j >= 0; j--) {
      if (pos[i].size() - j <= 2) {
        to[pos[i][j]] = n + 10;
      } else {
        if (pos[i][j] - pos[i][j + 1] == pos[i][j + 1] - pos[i][j + 2]) {
          to[pos[i][j]] = to[pos[i][j + 1]];
        } else {
          to[pos[i][j]] = pos[i][j + 2] - 1;
        }
      }
    }
    wtf.upd(pos[i][0], 1);
    upd(pos[i][0], to[pos[i][0]]);
  }
  std::sort(qries, qries + m);
  int p = 0;
  for (int i = 0; i < m; i++) {
    while (p < qries[i].l) {
      wtf.upd(p, -1);
      upd(p, -1);
      where[a[p]]++;
      if (where[a[p]] < pos[a[p]].size()) {
        upd(pos[a[p]][where[a[p]]], to[pos[a[p]][where[a[p]]]]);
        wtf.upd(pos[a[p]][where[a[p]]], 1);
      }
      p++;
    }
    ans[qries[i].idx] = wtf.qry(qries[i].r) + 1;
    if (qry(qries[i].l, qries[i].r + 1) >= qries[i].r) ans[qries[i].idx]--;
  }
  for (int i = 0; i < m; i++) {
    std::cout << ans[i] << '\n';
  }
}
