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;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
template <typename T>
bool chmax(T &x, const T &y) {
  return (x < y) ? (x = y, true) : false;
};
template <typename T>
bool chmin(T &x, const T &y) {
  return (x > y) ? (x = y, true) : false;
};
struct io_setup {
  io_setup() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(15);
  }
} io_setup;
struct query {
  int l, r, id;
  query(int l, int r, int id) : l(l), r(r), id(id) {}
};
int MAX = 100000;
template <typename T, typename Q>
struct Mo {
  vector<T> a;
  const int n;
  int l, r;
  vector<deque<int>> que;
  vector<vector<ll>> s;
  vector<int> p, q;
  Q sp, sq;
  Mo(vector<T> a)
      : a(a),
        n(a.size()),
        l(0),
        r(0),
        que(MAX),
        s(3, vector<ll>(MAX, 0)),
        p(MAX),
        q(MAX),
        sp(0),
        sq(0) {}
  bool judge(ll x, ll y, ll z) {
    if (x == 0) return true;
    if (y % x != 0) return false;
    ll k = y / x;
    return z == k * k * x;
  }
  void add_left(int i) {
    T x = a[i];
    if (que[x].empty()) {
      que[x].push_front(i), p[x]++, q[x]++, sp++, sq++;
    } else {
      ll d = que[x].front() - i, now = 1;
      for (int j = 0; j < 3; j++) {
        s[j][x] += now, now *= d;
      }
      que[x].push_front(i), p[x]++;
      if (q[x] == 1) {
        if (!judge(s[0][x], s[1][x], s[2][x])) {
          q[x]--, sq--;
        }
      }
    }
  }
  void add_right(int i) {
    T x = a[i];
    if (que[x].empty()) {
      que[x].push_back(i), p[x]++, q[x]++, sp++, sq++;
    } else {
      ll d = i - que[x].back(), now = 1;
      for (int j = 0; j < 3; j++) {
        s[j][x] += now, now *= d;
      }
      que[x].push_back(i), p[x]++;
      if (q[x] == 1) {
        if (!judge(s[0][x], s[1][x], s[2][x])) {
          q[x]--, sq--;
        }
      }
    }
  }
  void erase_left(int i) {
    T x = a[i];
    if ((int)que[x].size() == 1) {
      que[x].pop_front(), p[x]--, q[x]--, sp--, sq--;
    } else {
      que[x].pop_front(), p[x]--;
      ll d = que[x].front() - i, now = 1;
      for (int j = 0; j < 3; j++) {
        s[j][x] -= now, now *= d;
      }
      if (q[x] == 0) {
        if (judge(s[0][x], s[1][x], s[2][x])) {
          q[x]++, sq++;
        }
      }
    }
  }
  void erase_right(int i) {
    T x = a[i];
    if ((int)que[x].size() == 1) {
      que[x].pop_back(), p[x]--, q[x]--, sp--, sq--;
    } else {
      que[x].pop_back(), p[x]--;
      ll d = i - que[x].back(), now = 1;
      for (int j = 0; j < 3; j++) {
        s[j][x] -= now, now *= d;
      }
      if (q[x] == 0) {
        if (judge(s[0][x], s[1][x], s[2][x])) {
          q[x]++, sq++;
        }
      }
    }
  }
  vector<Q> solve(int bucket_size, vector<query> qs) {
    vector<Q> ret(qs.size());
    sort(begin(qs), end(qs), [&](query a, query b) {
      int A = (a.l) / bucket_size, B = (b.l) / bucket_size;
      if (A != B) return A < B;
      if (A % 2 == 0) return a.r < b.r;
      return a.r > b.r;
    });
    for (auto &e : qs) {
      while (e.l < l) add_left(--l);
      while (r < e.r) add_right(r++);
      while (l < e.l) erase_left(l++);
      while (e.r < r) erase_right(--r);
      ret[e.id] = sp + (sq == 0 ? 1 : 0);
    }
    return ret;
  }
};
int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    a[i]--;
  }
  Mo<int, int> mo(a);
  int Q;
  cin >> Q;
  vector<query> qs;
  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    qs.emplace_back(l, r, i);
  }
  for (auto &e : mo.solve(300, qs)) {
    cout << e << '\n';
  }
}
