#include <algorithm>
#include <cmath>
#include <iostream>

using std::cin;
using std::cout;

#define N 30005
#define Q 200005
#define INT 1000006

int lis[N];
int n, q;

int block, idx, hav;

struct ele {
    int l, r;
    int id;
    int block_id;

    void read(int idx) {
        block_id = (l - 1) / block + 1;
        id = idx;
        cin >> l >> r;
    }

    void debug() {
        cout << "id: " << id << " l: " << l << " r: " << r << " blockid: " << block_id << '\n';
    }
} que[Q];

int cnt[INT];
int res;
int ans[Q];

void ins(int x) {
    if (!cnt[lis[x]]) ++res;
    ++cnt[lis[x]];
}

void del(int x) {
    --cnt[lis[x]];
    if (!cnt[lis[x]]) --res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> lis[i];
    cin >> q;
    block = sqrt(n);
    idx = 1;
    for (int i = 1; i <= q; ++i) {
        if (hav > block) {
            hav = 0;
            ++idx;
        }
        ++hav;
        que[i].read(i);
    }
    std::sort(que + 1, que + q + 1, [](ele& a, ele& b) {
        if (a.block_id == b.block_id) {
            return (a.block_id & 1) ? a.r < b.r : a.r > b.r;
        } else
            return a.block_id < b.block_id;
    });
    int l, r;
    l = r = 0;
    for (int i = 1; i <= q; ++i) {
        int ql = que[i].l, qr = que[i].r;
        while (l < ql)
            del(l++);
        while (l > ql)
            ins(--l);
        while (r > qr)
            del(r--);
        while (r < qr)
            ins(++r);
        ans[que[i].id] = res;
    }

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

    return 0;
}