#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <queue>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <tuple>
#include <iomanip>
#include <stdio.h>
#include <map>
#include <bitset>
#include <set>
#include <stack>
#include <queue>
#include <unordered_set>
#include <cassert>
#include <stdlib.h>
#include <time.h>
#include <random>


//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

//#define int long long
#define ll long long
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pb push_back
#define ld long double


using namespace std;

//const int INF = 1e17;
//const int mod = 2600000069;
//const int p = 179;
int b;

struct event {
    int l, r, ind;
    event() {}
    event(int l_, int r_, int ind_) {l = l_; r = r_; ind = ind_;}
};

bool comp(const event &a, const event &b) {
    return a.r < b.r;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    b = sqrt(n) + 1;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<event> e[b];
    int q;
    cin >> q;
    event help;
    for (int i = 0; i < q; i++) {
        cin >> help.l >> help.r;
        help.ind = i;
        help.l--;help.r--;
        e[help.l / b].pb(help);
    }
    int kek[q];
    map<int, int> cnt;
    int l, r, ans;
    for (int i = 0; i < b; i++) {
        sort(all(e[i]), comp);
        l = i * b, r = i * b - 1, ans = 0;
        cnt.clear();
        for (auto k : e[i]) {
            while (r < k.r) {
                r++;
                cnt[a[r]]++;
                if (cnt[a[r]] == 1) ans++;
            }
            while (l > k.l) {
                l--;
                cnt[a[l]]++;
                if (cnt[a[l]] == 1) ans++;
            }
            while (l < k.l) {
                cnt[a[l]]--;
                if (cnt[a[l]] == 0) ans--;
                l++;
            }
            kek[k.ind] = ans;
        }
    }
    for (auto k : kek) cout << k << "\n";
}
/*
2
0 1 2 1
0 3 2 3

2
0 0 0 1
0 1 0 2

3
0 1 2 1
0 3 2 3
1 4 1 2


*/