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(100010);
int m, q, t;
int l[3 * N], r[3 * N], s[3 * N], rr[3 * N], del[3 * N];
int a[N], c[N], ans[N], pre[N], p[N];
bool cmp1(int x, int y) { return a[x] < a[y] || a[x] == a[y] && x < y; }
bool cmp2(int x, int y) { return l[x] < l[y] || l[x] == l[y] && x > y; }
bool cmp3(int x, int y) { return l[x] < l[y] || l[x] == l[y] && x < y; }
int low(int x) { return x & -x; }
void add(int x, int v) {
  for (; x <= m; x += low(x)) c[x] += v;
}
int sum(int x) {
  int ret = 0;
  for (; x; x -= low(x)) ret += c[x];
  return ret;
}
int main() {
  scanf("%d", &m);
  for (int i = int(1); i < int(m + 1); ++i) {
    scanf("%d", &a[i]);
    s[i] = i;
  }
  scanf("%d", &q);
  t = q;
  sort(s + 1, s + m + 1, cmp1);
  for (int i = 1, j = 1; i <= m; i = j) {
    int tt = 0;
    p[tt++] = 0;
    for (; j <= m && a[s[i]] == a[s[j]]; ++j) {
      pre[s[j]] = p[tt - 1];
      p[tt++] = s[j];
    }
    p[tt++] = m + 1;
    for (int x = 1, y = 1; x < tt - 1; ++x) {
      for (; p[x + 1] - p[x] == p[y + 1] - p[y] && y < tt - 2; ++y)
        ;
      l[t] = p[x - 1] + 1;
      r[t] = p[x];
      rr[t] = p[y + 1];
      del[t++] = 1;
      l[t] = p[x] + 1;
      r[t] = p[x];
      rr[t] = p[y + 1];
      del[t++] = -1;
    }
  }
  for (int i = int(0); i < int(q); ++i) scanf("%d%d", &l[i], &r[i]);
  for (int i = int(0); i < int(t); ++i) s[i] = i;
  sort(s, s + t, cmp2);
  int rmax = -1;
  for (int i = int(0); i < int(t); ++i)
    if (s[i] >= q) {
      add(r[s[i]], del[s[i]]);
      add(rr[s[i]], -del[s[i]]);
    } else if (sum(r[s[i]]) == 0)
      ++ans[s[i]];
  t = q;
  for (int i = int(1); i < int(m + 1); ++i) {
    l[t] = pre[i];
    r[t++] = i;
  }
  for (int i = int(0); i < int(t); ++i) s[i] = i;
  sort(s, s + t, cmp3);
  memset(c, 0, sizeof(c));
  for (int i = int(0); i < int(t); ++i)
    if (s[i] >= q)
      add(r[s[i]], 1);
    else
      ans[s[i]] += sum(r[s[i]]) - sum(l[s[i]] - 1);
  for (int i = int(0); i < int(q); ++i) printf("%d\n", ans[i]);
  return 0;
}
