#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1000010;

int n, a[N];
int m, len, cnt[N];
int ans[N];

int get(int x) { //分块
    return x / len;
}

struct node { // 左端点以块号排序，右端点从小到大排
    int id, l, r;
    bool operator < (const node &x) const {
        int a = get(l), b = get(x.l);
        if (a != b) return a < b;
        return r < x.r;
    }
}s[N];

void add(int x, int& res) {// 加
    if (!cnt[x]) res ++;
    cnt[x] ++;
}

void del(int x, int& res) {// 减
    cnt[x] --;
    if (!cnt[x]) res --;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

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

    cin >> m;
    len = sqrt(n);

    for (int i = 1; i <= m; i ++) {
        int l, r;
        cin >> l >> r;
        s[i] = {i, l, r};
    }

    sort(s + 1, s + m + 1);// 对询问排序

    for (int k = 1, i = 0, j = 1, res = 0; k <= m; k ++) { // 指针来回挪
        int id = s[k].id, l = s[k].l, r = s[k].r;
        while (i < r) add(a[++ i], res);
        while (i > r) del(a[i --], res);
        while (j < l) del(a[j ++], res);
        while (j > l) add(a[-- j], res);
        ans[id] = res;
    }

    for (int i = 1; i <= m; i ++) {
        cout << ans[i] << '\n';
    }

    return 0;
}