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;
struct _ {
  _() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  }
  stringstream ss;
} _;
template <class A, class B>
ostream& operator<<(ostream& o, pair<A, B> t) {
  o << "(" << t.first << ", " << t.second << ")";
  return o;
}
template <class T>
inline string tostring(T first) {
  _.ss.clear();
  _.ss.str("");
  _.ss << first;
  return _.ss.str();
}
template <class T>
inline T convert(const string& s) {
  char* p;
  if (is_integral<T>())
    return strtoll(s.c_str(), &p, 10);
  else
    return strtod(s.c_str(), &p);
}
template <class T>
void PV(T a, T b, int p = 0, int w = 0, string s = " ") {
  int c = 0;
  while (a != b) {
    cout << setw(w) << *a++;
    cout << ((a != b && (!p || ++c % p)) ? s : "\n");
  }
  cout.flush();
}
template <class T>
inline bool chmin(T& a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
inline bool chmax(T& a, T b) {
  return a < b ? a = b, 1 : 0;
}
const long long linf = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = int(1e9) + 7;
const int N = 100010;
int n, q;
int a[N];
int cnt[N];
deque<int> g[N];
map<int, int> df[N];
int same[N];
int cntSame;
int distinct;
namespace MO {
const static int S = 320;
int ans;
inline void add(int pos, int front) {
  int first = a[pos];
  auto& B = g[first];
  if (B.size() == 0) {
    distinct++;
    cntSame++;
    same[first] = 1;
    B.push_back(pos);
    return;
  }
  if (front) {
    df[first][B.front() - pos]++;
    B.push_front(pos);
  } else {
    df[first][pos - B.back()]++;
    B.push_back(pos);
  }
  if (same[first] && df[first].size() > 1) {
    same[first] = 0;
    cntSame--;
  }
}
inline void del(int pos, int front) {
  int first = a[pos];
  auto& B = g[first];
  if (B.size() == 1) {
    distinct--;
    cntSame--;
    same[first] = 0;
    B.pop_back();
    return;
  }
  if (front) {
    B.pop_front();
    auto it = df[first].find(B.front() - pos);
    it->second--;
    if (it->second == 0) df[first].erase(it);
  } else {
    B.pop_back();
    auto it = df[first].find(pos - B.back());
    it->second--;
    if (it->second == 0) df[first].erase(it);
  }
  if (same[first] == 0 && df[first].size() <= 1) {
    same[first] = 1;
    cntSame++;
  }
}
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
  int A = a.first.first / S, B = b.first.first / S;
  if (A != B) return A < B;
  return (A & 1) ? a.first.second < b.first.second
                 : a.first.second > b.first.second;
}
vector<int> queryOffline(vector<pair<pair<int, int>, int>> q) {
  vector<int> res(q.size());
  sort((q).begin(), (q).end(), cmp);
  ans = 0;
  int pl = 1, pr = 0;
  for (auto t : q) {
    int l = t.first.first, r = t.first.second, id = t.second;
    while (pr < r) add(++pr, 0);
    while (pl > l) add(--pl, 1);
    while (pr > r) del(pr--, 0);
    while (pl < l) del(pl++, 1);
    ans = distinct;
    if (cntSame == 0) ans++;
    res[id] = ans;
  }
  return res;
}
};  // namespace MO
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cin >> q;
  vector<pair<pair<int, int>, int>> query;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    query.push_back(make_pair(make_pair(l, r), i));
  }
  vector<int> res = MO::queryOffline(query);
  PV((res).begin(), (res).end(), 1);
  cerr << "{"
          "0"
          " -> "
          "clock()"
          ": "
       << 1000 * (clock() - 0) / CLOCKS_PER_SEC << "ms}\n";
  ;
  return 0;
}
