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>
using namespace std;
const int N = 4e5 + 100;
const long long int inf = 1e17;
int n;
long long int sum[N], mn[N], a[N], b[N], la[N], k[N], ans[N];
vector<pair<pair<int, int>, int>> v;
void add(int x, long long int val, int b = 0, int e = n, int ind = 1) {
  if (b + 1 == e) {
    mn[ind] = val;
    return;
  }
  int mid = (b + e) / 2;
  if (x < mid)
    add(x, val, b, mid, ind * 2);
  else
    add(x, val, mid, e, ind * 2 + 1);
  mn[ind] = min(mn[ind * 2], mn[ind * 2 + 1]);
}
long long int get(int l, int r, int b = 0, int e = n, int ind = 1) {
  if (b >= r || e <= l) return inf;
  if (l <= b && e <= r) return mn[ind];
  int mid = (b + e) / 2;
  return min(get(l, r, b, mid, ind * 2), get(l, r, mid, e, ind * 2 + 1));
}
void add2(int x, long long int val, int b = 0, int e = n, int ind = 1) {
  if (b + 1 == e) {
    sum[ind] = val;
    return;
  }
  int mid = (b + e) / 2;
  if (x < mid)
    add2(x, val, b, mid, ind * 2);
  else
    add2(x, val, mid, e, ind * 2 + 1);
  sum[ind] = sum[ind * 2] + sum[ind * 2 + 1];
}
long long int get2(int l, int r, int b = 0, int e = n, int ind = 1) {
  if (b >= r || e <= l) return 0;
  if (l <= b && e <= r) return sum[ind];
  int mid = (b + e) / 2;
  return get2(l, r, b, mid, ind * 2) + get2(l, r, mid, e, ind * 2 + 1);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    v.push_back({{r, l}, i});
  }
  sort(v.begin(), v.end());
  int j = 0;
  for (int i = 0; i < n; i++) b[a[i]] = -1;
  for (int i = 0; i < n; i++) {
    int x = a[i];
    if (b[x] != -1) {
      int jj = b[x];
      add2(jj, 0);
      add(jj, inf);
      la[i] = jj;
      if (la[jj] != -1 && la[jj] - jj != jj - i)
        k[i] = la[jj] + 1;
      else
        k[i] = k[jj];
    } else {
      k[i] = -1;
      la[i] = -1;
    }
    add2(i, 1);
    add(i, k[i]);
    while (j != q && v[j].first.first == i + 1) {
      int l = v[j].first.second, r = v[j].first.first, id = v[j].second;
      long long int m = get(l, r);
      ans[id] = get2(l, r);
      if (m > l) ans[id]++;
      j++;
    }
    b[x] = i;
  }
  for (int i = 0; i < q; i++) cout << ans[i] << endl;
  return 0;
}
