const int k = 600;
struct query { int l, r, i; };

istream& operator>>(istream &in, query &q) {
    in >> q.l >> q.r;
    return in;
}

int main() {
    fast
    // file_in
    // file_in_out

    int n, m;
    cin >> n;
    vector<int> a(n);
    cin >> a >> m;

    vector<int> b = a;
    sort(all(b));
    gp_hash_table<int, int> get;
    for (int i = 0; i < n; ++i) if (!get[b[i]]) get[b[i]] = i + 1;

    vector<query> querys(m);
    vector<vector<query>> c(n / k + 1);
    vector<int> ans(m);
    cin >> querys;
    for (int i = 0; i < m; ++i) {
        querys[i].l--; querys[i].r--;
        querys[i].i = i;
        c[querys[i].l / k].push_back(querys[i]);
    }

    for (int i = 0; i < sz(c); ++i) {
        sort(all(c[i]), [](query q1, query q2){
            return q1.r < q2.r;
        });
    }
    for (int i = 0; i < sz(c); ++i) {
        vector<int> ht(n + 1);
        int l = i * k, r = i * k - 1, cnt = 0;
        for (auto q : c[i]) {
            while (r < q.r) {
                ++r;
                if (!ht[get[a[r]]]) ++cnt;
                ht[get[a[r]]]++;
            }
            while (l < q.l) {
                ht[get[a[l]]]--;
                if (!ht[get[a[l]]]) --cnt;
                ++l;
            }
            while (l > q.l) {
                --l;
                if (!ht[get[a[l]]]) ++cnt;
                ht[get[a[l]]]++;
            }
            ans[q.i] = cnt;
        }
    }
    for (auto el : ans) cout << el << '\n';
    return 0;
}