#include <bits/stdc++.h>

using namespace std;

const int MAXN = 30005;
const int MAXVAL = 1000005;

int bit[MAXN];
int a[MAXN];
int last_pos[MAXVAL]; 
int ans[200005];     
int n, q;


struct Query {
    int l, r, id;
    bool operator<(const Query& other) const {
        return r < other.r;
    }
};

void update(int idx, int val) {
    for (; idx <= n; idx += idx & -idx)
        bit[idx] += val;
}

int getSum(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx)
        sum += bit[idx];
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cin >> q;
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i; 
    }
    sort(queries.begin(), queries.end());
    int current_query = 0;
    for (int i = 1; i <= n; i++) {
        int val = a[i];
        if (last_pos[val] != 0) {
            update(last_pos[val], -1);
        }
        update(i, 1);
        last_pos[val] = i;
        while (current_query < q && queries[current_query].r == i) {
            int L = queries[current_query].l;
            int R = queries[current_query].r;
            int query_id = queries[current_query].id;
            ans[query_id] = getSum(R) - getSum(L - 1);
            current_query++;
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}