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

struct Query {
    int l, r, id;
};

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 2, 0) {}

    void add(int i, int v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }

    void range_add(int l, int r, int v) {
        if (l > r) return;
        add(l, v);
        add(r + 1, -v);
    }

    int get(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
};

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

    int n, q, c;
    cin >> n >> q >> c;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    unordered_map<int, vector<int>> pos;

    for (int i = 1; i <= n; i++) {
        if (a[i] <= n) {
            pos[a[i]].push_back(i);
        }
    }

    vector<vector<pair<int,int>>> addEvents(n + 2), removeEvents(n + 2);

    for (auto &[x, v] : pos) {
        int k = v.size();

        for (int i = 0; i + x - 1 < k; i++) {
            int first = v[i];
            int last = v[i + x - 1];

            int Lmin = (i == 0 ? 1 : v[i - 1] + 1);
            int Lmax = first;

            int Rstart = last;
            int Rend = (i + x < k ? v[i + x] - 1 : n);

            addEvents[Rstart].push_back({Lmin, Lmax});

            if (Rend + 1 <= n) {
                removeEvents[Rend + 1].push_back({Lmin, Lmax});
            }
        }
    }

    sort(queries.begin(), queries.end(), [](const Query &A, const Query &B) {
        return A.r < B.r;
    });

    Fenwick fw(n);
    vector<int> ans(q);

    int curR = 1;

    for (auto &qu : queries) {
        while (curR <= qu.r) {
            for (auto [l, r] : addEvents[curR]) {
                fw.range_add(l, r, +1);
            }

            for (auto [l, r] : removeEvents[curR]) {
                fw.range_add(l, r, -1);
            }

            curR++;
        }

        ans[qu.id] = fw.get(qu.l);
    }

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

    return 0;
}
