#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <queue>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <tuple>
#include <iomanip>
#include <stdio.h>
#include <map>
#include <bitset>
#include <set>
#include <stack>
#include <queue>
#include <unordered_set>
#include <cassert>
#include <stdlib.h>
#include <time.h>
#include <random>


//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

//#define int long long
#define ll long long
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pb push_back
#define ld long double


using namespace std;

//const int INF = 1e17;
//const int mod = 2600000069;
//const int p = 179;
int sq = 550;

struct event {
    int l, r, ind;
    event() {}
    event(int l_, int r_, int ind_) {l = l_; r = r_; ind = ind_;}
};

bool comp(const event &a, const event &b) {
    return a.r < b.r;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b = a;
    sort(all(b));
    b.resize(unique(all(b)) - b.begin());
    map<int, int> real;
    int sz = b.size();
    for (int i = 0; i < sz; i++) {
        real[b[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        a[i] = real[a[i]];
    }
    vector<vector<event>> c(sq);
    int q;
    cin >> q;
    int l, r;
    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        l--;r--;
        c[l / sq].pb(event(l, r, i));
    }
    vector<int> kek(q, 0);
    vector<int> cnt;
    int ans;
    for (int i = 0; i < sq; i++) {
        if (c[i].empty()) continue;
        cnt.assign(sz, 0);
        sort(all(c[i]), comp);
        ans = 0;
        l = i * sq;
        r = i * sq - 1;
        for (auto k : c[i]) {
            while (r < k.r) {
                r++;
                cnt[a[r]]++;
                if (cnt[a[r]] == 1) ans++;
            }
            while(l > k.l) {
                l--;
                cnt[a[l]]++;
                if (cnt[a[l]] == 1) ans++;
            }
            while (l < k.l) {
                cnt[a[l]]--;
                if (cnt[a[l]] == 0) ans--;
                l++;
            }
            kek[k.ind] = ans;
        }
    }
    for (auto k : kek) cout << k << "\n";
}
/*
2
0 1 2 1
0 3 2 3

2
0 0 0 1
0 1 0 2

3
0 1 2 1
0 3 2 3
1 4 1 2


*/