#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>



template<class T>
struct Fen {
    int n;
    vector<T> t;
    Fen (int n_) {
        init(n_);
    }
    Fen () {};
    void init(int n_) {
        n = n_;
        t.assign(n + 1, {});
    }
    void change(int u, T x) {
        for(; u <= n; u += u & -u) t[u] += x;
    }
    T sum(int u) {
        T res = 0;
        for(; u; u -= u & -u) res += t[u];
        return res;
    }
    T sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    int kth(T sum) {
        int i = 0;
        T tot = {};
        for (int j = 1 << __lg(n); j > 0; j /= 2) {
            if (i + j <= n && t[i + j] + tot < sum) {
                i += j;
                tot += t[i];
            }
        }
        return i + 1;
    }
};

void solve() {
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    const int N = 1e6;
    vector<int> suf(n + 1), pos(N + 1, n + 1);

    vector<pii> o;
    for (int i = n; i >= 1; i--) {
        suf[i] = pos[a[i]];
        pos[a[i]] = i;
        o.push_back({suf[i], i});
    }
    /*
    sufi > r
    l <= i <= r
    */
    sort(o.begin(), o.end(), greater<pii>());

    vector q(n + 1, vector<pii>());
    int m; cin >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        q[r].push_back({l, i});
    }

    vector<int> ans(m + 1);
    Fen<int> t(n);
    for (int r = n, j = 0; r >= 1; r--) {
        cerr << r << endl;
        while (j < o.size() && o[j].first > r) {
            t.change(o[j].second, 1);
            j++;
        }
        for (auto [l, id] : q[r]) {
            ans[id] = t.sum(l, r);
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';

}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
/*
g++ -std=c++17 1.cpp -o 1 && 1 < in.txt > out.txt
g++ -std=c++17 1.cpp -o 1 && ./1 < in.txt > out.txt

*/