#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n, m, c;
	cin >> n >> m >> c;
	int a[n], ans[m]{}, bit[n + 1]{};
	vector<pair<int, int>> q[n];
	vector<int> pos[n + 1];
	for (int &i : a) cin >> i;
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		q[y - 1].emplace_back(x - 1, i);
	}
	for (int i = 0; i < n; ++i) {
		if (a[i] <= n) {
			if (pos[a[i]].size() >= a[i] + 1)
				for (int j = pos[a[i]][pos[a[i]].size() - a[i] - 1]; j <= n; j += j & -j)
					++bit[j];
			if (pos[a[i]].size() >= a[i])
				for (int j = pos[a[i]][pos[a[i]].size() - a[i]]; j <= n; j += j & -j)
					bit[j] -= 2;
			pos[a[i]].push_back(i + 1);
			if (pos[a[i]].size() >= a[i])
				for (int j = pos[a[i]][pos[a[i]].size() - a[i]]; j <= n; j += j & -j)
					++bit[j];
		}
		for (auto j : q[i]) {
			for (int ii = i + 1; ii; ii -= ii & -ii)
				ans[j.second] += bit[ii];
			for (int ii = j.first; ii; ii -= ii & -ii)
				ans[j.second] -= bit[ii];
		}
	}
	for (int i : ans) cout << i << '\n';
}
