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 long long maxn = 1e5 + 500;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 500;
long long a[maxn];
long long fen[maxn][2];
pair<pair<long long, long long>, long long> que[maxn];
long long ans[maxn];
long long o[maxn];
long long nextt[maxn];
bool yek[maxn];
void update(long long x, long long val, bool v) {
  x++;
  while (x < maxn) {
    fen[x][v] += val;
    x += (x & (-x));
  }
}
long long finds(long long x, bool v) {
  x++;
  long long ans = 0;
  while (x > 0) {
    ans += fen[x][v];
    x -= (x & (-x));
  }
  return ans;
}
int main() {
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  fill(o, o + maxn, -1);
  for (long long i = 0; i < n; i++) {
    if (o[a[i]] == -1) {
      update(i, 1, 0);
      o[a[i]] = i;
    } else {
      nextt[o[a[i]]] = i;
      o[a[i]] = i;
    }
  }
  fill(o, o + maxn, 0);
  for (long long i = 0; i < n; i++) {
    if (nextt[i] != 0) {
      o[nextt[i]] = 1;
    }
  }
  for (long long i = 0; i < n; i++) {
    if (o[i] == 0) {
      if (nextt[i] != 0) {
        long long t = nextt[i] - i;
        long long p = nextt[i];
        while (nextt[p] != 0 && nextt[p] - p == t) {
          p = nextt[p];
        }
        if (nextt[p] != 0) {
          update(nextt[p], 1, 1);
          yek[nextt[p]] = 1;
        }
      }
    }
  }
  long long m;
  cin >> m;
  for (long long i = 0; i < m; i++) {
    long long l, r;
    cin >> l >> r;
    l--;
    r--;
    que[i] = make_pair(make_pair(l, r), i);
  }
  sort(que, que + m);
  long long p = 0;
  for (long long i = 0; i < m; i++) {
    while (p < que[i].first.first) {
      update(p, -1, 0);
      if (nextt[p] != 0) {
        update(nextt[p], 1, 0);
      }
      if (nextt[p] != 0 && nextt[nextt[p]] != 0) {
        long long a1 = nextt[p];
        long long a2 = nextt[a1];
        if (yek[a2]) {
          update(a2, -1, 1);
          long long t = a2 - a1;
          long long pp = a2;
          while (nextt[pp] != 0 && nextt[pp] - pp == t) {
            pp = nextt[pp];
          }
          if (nextt[pp] != 0) {
            update(nextt[pp], 1, 1);
            yek[nextt[pp]] = 1;
          }
        }
      }
      p++;
    }
    long long v = finds(que[i].first.second, 0);
    long long u = finds(que[i].first.second, 1);
    if (u == v) {
      ans[que[i].second] = v + 1;
    } else {
      ans[que[i].second] = v;
    }
  }
  for (long long i = 0; i < m; i++) {
    cout << ans[i] << endl;
  }
}
