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

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

int main() {
    fast
    // file_in

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

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