#include <bits/stdc++.h>   using namespace std;   const int M = (int)1e5 + 5;   int n;   int a[M];   int q, ans[M];   vector<pair<int, int> > ps[M];   int pas[M], las[M], llas[M], mfr[M];   struct SEGMENT1 {     int val[M * 4];     void update(int L, int R, int p, int l, int r, int v) {       if (L == l && R == r) {         val[p] += v;         return;       }       int mid = (L + R) >> 1;       if (mid >= r)         update(L, mid, p << 1, l, r, v);       else if (mid < l)         update(mid + 1, R, p << 1 | 1, l, r, v);       else         update(L, mid, p << 1, l, mid, v),             update(mid + 1, R, p << 1 | 1, mid + 1, r, v);     }     int query(int L, int R, int p, int x) {       if (L == R) return val[p];       int mid = (L + R) >> 1;       if (mid >= x)         return val[p] + query(L, mid, p << 1, x);       else         return val[p] + query(mid + 1, R, p << 1 | 1, x);     }   } T1;   struct SEGMENT2 {     int val[M * 4];     void update(int L, int R, int p, int x, int v) {       val[p] += v;       if (L == R) return;       int mid = (L + R) >> 1;       if (mid >= x)         update(L, mid, p << 1, x, v);       else         update(mid + 1, R, p << 1 | 1, x, v);     }     int query(int L, int R, int p, int l, int r) {       if (L == l && R == r) return val[p];       int mid = (L + R) >> 1;       if (mid >= r)         return query(L, mid, p << 1, l, r);       else if (mid < l)         return query(mid + 1, R, p << 1 | 1, l, r);       else         return query(L, mid, p << 1, l, mid) +                query(mid + 1, R, p << 1 | 1, mid + 1, r);     }   } T2;   int main() {     scanf( %d , &n);     for (int i = 1; i <= n; i++) scanf( %d , &a[i]);     scanf( %d , &q);     for (int i = 1, l, r; i <= q; i++)       scanf( %d %d , &l, &r), ps[r].push_back(pair<int, int>(l, i));     for (int i = 1, x, len; i <= n; i++) {       x = a[i];       len = i - las[x];       if (len != pas[x] && pas[x] != las[x]) {         if (mfr[x] < llas[x]) T1.update(1, n, 1, mfr[x] + 1, llas[x], 1);         mfr[x] = llas[x];       }       pas[x] = len;       if (las[x] != 0) T2.update(1, n, 1, las[x], -1);       T2.update(1, n, 1, i, 1);       llas[x] = las[x];       las[x] = i;       for (int j = 0, up = ps[i].size(), c1, c2, l, id; j < up; j++) {         l = ps[i][j].first;         id = ps[i][j].second;         c1 = T2.query(1, n, 1, l, i);         c2 = T1.query(1, n, 1, l);         if (c1 != c2)           ans[id] = c1;         else           ans[id] = c1 + 1;       }     }     for (int i = 1; i <= q; i++) printf( %d n , ans[i]);     return 0;   }   