#include <bits/stdc++.h>   using namespace std;   struct number {     deque<int> q;     map<int, int> db;     int curr = 0;   };   struct pii {     int x, y, id;   };   const int S = 300;   bool sortFunc(pii a, pii b) {     if (a.x / S == b.x / S) return ((a.x / S) & 1 ? a.y > b.y : a.y < b.y);     return a.x < b.x;   }   vector<number> t(1e5 + 1);   void inc(map<int, int>& db, int num, int& curr) {     if (db.count(num) == 0) db[num] == 0;     if (++db[num] == 1) curr++;   }   void dec(map<int, int>& db, int num, int& curr) {     if (--db[num] == 0) curr--;   }   int curr = 0, nums = 0;   void add(int poz, int num) {     if (t[num].curr <= 1 && t[num].q.size() > 0) curr--;     if (t[num].q.empty())       t[num].q.push_front(poz);     else if (poz < t[num].q.front()) {       inc(t[num].db, t[num].q.front() - poz, t[num].curr);       t[num].q.push_front(poz);     } else {       inc(t[num].db, poz - t[num].q.back(), t[num].curr);       t[num].q.push_back(poz);     }     if (t[num].curr <= 1) curr++;     if (t[num].q.size() == 1) nums++;   }   void remove(int poz, int num) {     if (t[num].curr <= 1) curr--;     if (t[num].q.size() == 1)       t[num].q.pop_front();     else if (poz == t[num].q.front()) {       t[num].q.pop_front();       dec(t[num].db, t[num].q.front() - poz, t[num].curr);     } else {       t[num].q.pop_back();       dec(t[num].db, poz - t[num].q.back(), t[num].curr);     }     if (t[num].curr <= 1 && t[num].q.size() > 0) curr++;     if (t[num].q.size() == 0) nums--;   }   int main() {     int n;     cin >> n;     vector<int> sor(n);     for (int& a : sor) cin >> a;     int q;     cin >> q;     vector<pii> v(q);     for (int i = 0; i < q; i++)       cin >> v[i].x >> v[i].y, v[i].id = i, v[i].x--, v[i].y--;     sort(v.begin(), v.end(), sortFunc);     int l = 0, r = -1;     vector<int> ans(q);     for (pii& a : v) {       while (a.x < l) add(l - 1, sor[l - 1]), l--;       while (r < a.y) add(r + 1, sor[r + 1]), r++;       while (l < a.x) remove(l, sor[l]), l++;       while (a.y < r) remove(r, sor[r]), r--;       ans[a.id] = (curr > 0 ? nums : nums + 1);     }     for (int& a : ans) cout << a <<   n ;   }   