#include <bits/stdc++.h>
using namespace std;

#define sz(o) ((int)o.size())
#define all(o) o.begin(), o.end()
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repr(i, a, b) for(int i = (a); i >= (b); i--)

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<int> vi;

const int maxa = 1e6, maxq = 2e5;
struct Triplet{
    int l, r, idx;
};
Triplet range[maxq + 10];
int freq[maxa + 10];
int ans[maxq + 10], cur = 0, block;
vi a;

void fs(int &nn) {
    bool neg = false;
    register int ch;
    nn = 0;
    ch = getchar();
    if (ch == '-') {
        neg = true;
        ch = getchar();
    }
    for (; (ch > 47 && ch < 58); ch = getchar()) nn = nn * 10 + ch - 48;
    if (neg) nn *= -1;
}

void add(int idx){
    freq[a[idx]]++;
    if(freq[a[idx]] == 1) cur++;
}

void remove(int idx){
    freq[a[idx]]--;
    if(freq[a[idx]] == 0) cur--;
}

void solve() {
    int n, q;
    fs(n);
    block = ceil(sqrt(n));
    a.assign(n + 1, 0);
    rep(i, 1, n) fs(a[i]);
    fs(q);
    rep(i, 1, q){
        fs(range[i].l);
        fs(range[i].r);
        range[i].idx = i;
    }
    sort(range + 1, range + q + 1, [](const Triplet &a, const Triplet &b)->bool{
        if(a.l / block != b.l / block) return a.l / block < b.l / block;
        return a.r < b.r;
    });
    int mo_left = 0, mo_right = 0;
    rep(i, 1, q){
        while(mo_left < range[i].l){
            remove(mo_left);
            mo_left++;
        }
        while(mo_left > range[i].l){
            mo_left--;
            add(mo_left);
        }
        while(mo_right < range[i].r){
            mo_right++;
            add(mo_right);
        }
        while(mo_right > range[i].r){
            remove(mo_right);
            mo_right--;
        }
        ans[range[i].idx] = cur;
    }
    rep(i, 1, q) printf("%d\n", ans[i]);
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    /*ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);*/
    cout << setprecision(10);
    clock_t b = clock();
    solve();
    clock_t e = clock();
    cerr << (double(e - b) / CLOCKS_PER_SEC) << " sec";
    return 0;
}