#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define sino(b) cout<<(b ? "YES\n":"NO\n")
#define casos(t) int t; cin >> t; while(t--)
#define print(b) cout << (b) << endl
#define input(n, a) for(int i=0; i<n; ++i) cin>>a[i];
#define ln cout<<endl
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define forn(i,n) for(int i=0; i < int(n); ++i)
#define F first
#define S second
#define sz(x) int((x).size())
#define sDBG(x) for(auto &el : x) {cout << el << " ";} cout<<endl;
#define DBG(x) cout << #x << " = " << x << endl;
#define DBGMap(x) for(auto &el : x) {cout << el.F << ": " << el.S ;} cout<<endl;
#define all(i) i.begin(), i.end()
#define rall(x) (x).rbegin(), (x).rend()
#define stp(a,b) cout << fixed << setprecision(a) <<(b) << endl;
#define lw(c, x) int(lower_bound((c).begin(), (c).end(), (x)) - (c).begin())
#define up(c, x) int(upper_bound((c).begin(), (c).end(), (x)) - (c).begin())
#define kill(x) {cout << x << endl; return;}
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
typedef pair<long long ,long long> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;

const int MAXN = 2e5 + 5;
int arr[MAXN];
int freq[MAXN];
int cnt_distinct = 0;
int block_size;

void add(int idx) {
    int val = arr[idx];
    if (freq[val] == 0) cnt_distinct++;
    freq[val]++;
}

void remove(int idx) {
    int val = arr[idx];
    freq[val]--;
    if (freq[val] == 0) cnt_distinct--;
}

int get_answer() {
    return cnt_distinct;
}

struct Query {
    int l, r, idx;
    
    bool operator<(const Query& other) const {
        int b1 = l / block_size;
        int b2 = other.l / block_size;
        if (b1 != b2) return b1 < b2;
        return (b1 & 1) ? (r < other.r) : (r > other.r);
    }
};

void solve() {
    int n, q;
    
    forn(i, n) cin >> arr[i];

    block_size = max(1, (int)sqrt(n));

    vector<Query> queries(q);
    forn(i, q) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }

    sort(all(queries));

    vi ans(q);
    int cur_l = 0, cur_r = -1;
    cnt_distinct = 0;

    for (auto &q : queries) {
        while (cur_l > q.l) { cur_l--; add(cur_l); }
        while (cur_r < q.r) { cur_r++; add(cur_r); }
        while (cur_l < q.l) { remove(cur_l); cur_l++; }
        while (cur_r > q.r) { remove(cur_r); cur_r--; }

        ans[q.idx] = get_answer();
    }

    for (int i = cur_l; i <= cur_r; i++) freq[arr[i]] = 0;

    forn(i, q) print(ans[i]);
}

int main() {
    FastIO;
    solve();
    return 0;
}

// (づ｡◕‿‿◕｡)づ 1811