/*

#include <bits/stdc++.h>

using namespace std;

int main() {
    freopen("carici.in", "r", stdin);

    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);

    return 0;
}

 */

#include <bits/stdc++.h>

using namespace std;

#define NMAX 100001

int n, t;
map<int, int> position;
int tree[NMAX];

int cnt;
struct node {
    int val;
    int L, R;
    int size;
} nodes[2 * NMAX * 17]; // lg2 NMAX = 16,9...

int build(int lo, int hi) {
    if (lo > hi) return 0;

    int idx = ++cnt;
    int mid = (lo + hi) / 2;
    nodes[idx] = (node) {mid, build(lo, mid - 1), build(mid + 1, hi), 0};
    return idx;
}

int update(int x, int val, int amount) {
    if (x == 0) return 0;

    int idx = ++cnt;

    int L = nodes[x].L;
    int R = nodes[x].R;
    if (val < nodes[x].val) L = update(L, val, amount);
    if (val > nodes[x].val) R = update(R, val, amount);

    nodes[idx] = (node) {nodes[x].val, L, R, nodes[x].size + amount};

    return  idx;
}

int query(int x, int val) {
    if (val < nodes[x].val) {
        return query(nodes[x].L, val) + nodes[x].size - nodes[nodes[x].L].size;
    }

    if (val > nodes[x].val) {
        return query(nodes[x].R, val);
    }

    return nodes[x].size - nodes[nodes[x].L].size;
}

int main() {
    freopen("carici.in", "r", stdin);

    cin >> n;

    tree[0] = build(1, n);
    for (int i = 1; i <= n; i++) {
        int x, posx;
        cin >> x;

        posx = position[x];
        if (posx != 0) {
            tree[i] = update(update(tree[i - 1], posx, -1), i, 1);
        } else {
            tree[i] = update(tree[i - 1], i, 1);
        }
        position[x] = i;
    }

    cin >> t;
    int lo, hi;
    while (t--) {
        cin >> lo >> hi;
        cout << query(tree[hi], lo) << "\n";
    }

    return 0;
}