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

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

bool cmp(query &q1, query &q2) {
    if (q1.l / k == q2.l / k) {
        return q1.r < q2.r;
    }
    return q1.l < q2.l;
}

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> qq(m);
    cin >> qq;
    for (int i = 0; i < m; ++i) {
        qq[i].l--; qq[i].r--; qq[i].i = i;
    }
    sort(all(qq), cmp);

    vector<int> ans(m);
    int ht[n + 1];
    int l, r, cnt, c = -1;
    for (auto q : qq) {
        if (q.l / k != c) {
            for (int i = 0; i <= n; ++i) ht[i] = 0;
            l = q.l; r = q.r; cnt = 0;
            for (int i = l; i <= r; ++i) {
                if (!ht[get[a[i]]]) ++cnt;
                ht[get[a[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;
}