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>
#pragma GCC optimize("O2")
using namespace std;
const long long int mod = 1000000007;
const long long int INF64 = mod * mod + 1;
long long int sz;
bool compare(array<long long int, 3> a, array<long long int, 3> b) {
  if (a[0] / sz == b[0] / sz) return a[1] < b[1];
  return a[0] / sz < b[0] / sz;
}
void solve() {
  long long int n;
  cin >> n;
  const long long int mxN = 1e5;
  vector<vector<long long int>> pos(mxN + 1);
  vector<vector<long long int>> maxAP(mxN + 1);
  vector<long long int> a(n);
  for (long long int i = 0; i < n; i++) {
    cin >> a[i];
    pos[a[i]].push_back(i);
    maxAP[a[i]].push_back(0);
  }
  for (long long int i = 1; i <= mxN; i++) {
    assert(pos[i].size() == maxAP[i].size());
    if (maxAP[i].empty()) continue;
    maxAP[i].back() = 1;
    if (maxAP[i].size() > 1) maxAP[i][maxAP[i].size() - 2] = 2;
    for (long long int j = (long long int)maxAP[i].size() - 3; j >= 0; j--)
      maxAP[i][j] = max(2LL, ((pos[i][j] - pos[i][j + 1]) ==
                              (pos[i][j + 1] - pos[i][j + 2])) *
                                 (maxAP[i][j + 1] + 1LL));
  }
  long long int block = sqrt(n);
  sz = block;
  long long int q;
  cin >> q;
  vector<array<long long int, 3>> query(q);
  for (long long int i = 0; i < q; i++) {
    long long int l, r;
    cin >> l >> r;
    query[i] = {l - 1, r - 1, i};
  }
  sort((query).begin(), (query).end(), compare);
  vector<long long int> ans(q);
  vector<long long int> freq(mxN + 1, 0);
  vector<deque<long long int>> currpos(mxN + 1);
  set<long long int> currAPs;
  long long int currl = 0, currr = -1, uniq = 0;
  for (long long int i = 0; i < q; i++) {
    long long int l = query[i][0], r = query[i][1];
    while (currl > l) {
      currl--;
      currpos[a[currl]].push_front(currl);
      auto it = lower_bound((pos[a[currl]]).begin(), (pos[a[currl]]).end(),
                            currpos[a[currl]].front()) -
                pos[a[currl]].begin();
      if (maxAP[a[currl]][it] >= currpos[a[currl]].size())
        currAPs.insert(a[currl]);
      else
        currAPs.erase(a[currl]);
      freq[a[currl]]++;
      if (freq[a[currl]] == 1) uniq++;
    }
    while (currr < r) {
      currr++;
      currpos[a[currr]].push_back(currr);
      auto it = lower_bound((pos[a[currr]]).begin(), (pos[a[currr]]).end(),
                            currpos[a[currr]].front()) -
                pos[a[currr]].begin();
      if (maxAP[a[currr]][it] >= currpos[a[currr]].size())
        currAPs.insert(a[currr]);
      else
        currAPs.erase(a[currr]);
      freq[a[currr]]++;
      if (freq[a[currr]] == 1) uniq++;
    }
    while (currl < l) {
      freq[a[currl]]--;
      currpos[a[currl]].pop_front();
      if (freq[a[currl]] == 0) {
        uniq--;
        currAPs.erase(a[currl]);
      } else {
        auto it = lower_bound((pos[a[currl]]).begin(), (pos[a[currl]]).end(),
                              currpos[a[currl]].front()) -
                  pos[a[currl]].begin();
        if (maxAP[a[currl]][it] >= currpos[a[currl]].size())
          currAPs.insert(a[currl]);
        else
          currAPs.erase(a[currl]);
      }
      currl++;
    }
    while (currr > r) {
      freq[a[currr]]--;
      currpos[a[currr]].pop_back();
      if (freq[a[currr]] == 0) {
        uniq--;
        currAPs.erase(a[currr]);
      } else {
        auto it = lower_bound((pos[a[currr]]).begin(), (pos[a[currr]]).end(),
                              currpos[a[currr]].front()) -
                  pos[a[currr]].begin();
        if (maxAP[a[currr]][it] >= currpos[a[currr]].size())
          currAPs.insert(a[currr]);
        else
          currAPs.erase(a[currr]);
      }
      currr--;
    }
    ans[query[i][2]] = uniq + currAPs.empty();
  }
  for (auto it : ans) cout << it << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int T = 1;
  for (long long int i = 1; i <= T; i++) {
    solve();
  }
  cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
}
