#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
#include <string>
#include <set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <numeric>
#include <random>
#include <memory>
#include <chrono>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <cassert>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif
//#pragma GCC optimize("Ofast")
//#define int ll



using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
#define mp make_pair
#define pb push_back
#define sz(x) int((x).size())

#ifndef LOCAL
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#else
mt19937 rng(228);
#endif

const int N = 1e5 + 7;
const int inf = INT_MAX / 2;
const ll INF = LLONG_MAX / 3;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const string cars[] = {"🚗", "🚕", "🚙"};

struct Tree {
    private: int t[4 * N];
    private: int n;

    public: Tree(int n) : n(n) {}

    private: void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            t[v] = val;
        }
        else {
            int tm = (tl + tr) / 2;

            if (pos <= tm) {
                update(2 * v, tl, tm, pos, val);
            }
            else {
                update(2 * v + 1, tm + 1, tr, pos, val);
            }

            t[v] = t[2 * v] + t[2 * v + 1];
        }
    }

    public: void set(int pos, int val) {
        update(1, 0, n - 1, pos, val);
    }

    private: int ans(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (tl == l && tr == r) {
            return t[v];
        }

        int tm = (tl + tr) / 2;
        return ans(2 * v, tl, tm, l, min(tm, r)) + ans(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
    }

    public: int query(int l, int r) {
        return ans(1, 0, n - 1, l, r);
    }
};

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout << fixed << setprecision(9);
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    int n;
    cin >> n;

    vector < int > a(n);

    for (int& x : a) {
        cin >> x;
    }

    int q;
    cin >> q;

    vector < tuple < int, int, int > > b(q);

    for (int i = 0; i < q; i++) {
        auto& [x, y, id] = b[i];
        cin >> x >> y;
        x--, y--;
        id = i;
    }

    sort(b.begin(), b.end());
    map < int, int > last;
    int j = q - 1;
    Tree tree(n);
    vector < int > ans(q);

    for (int i = n - 1; i >= 0; i--) {
        int t = last[a[i]];
        if (t) {
            tree.set(t, 0);
        }

        tree.set(i, 1);
        last[a[i]] = i;

        while (j >= 0 && get < 0 > (b[j]) >= i) {
            ans[get < 2 > (b[j])] = tree.query(get < 0 > (b[j]), get < 1 > (b[j]));
            j--;
        }
    }

    for (int x : ans) {
        cout << x << "\n";
    }

    return 0;
}