#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;

class aib{
	int n;
	vector<int> buf;
public:
	aib(const int N): n(N), buf(n+1, 0){}
	void update(int p, const int d){
		for(++p; p <= n; p += p&-p){
			buf[p] += d; } }
	long long query(int p){
		long long rez = 0;
		for(++p; p > 0; p -= p&-p){
			rez += (long long)buf[p]; }
		return rez; }
	long long query(int st, int dr){
		return query(dr) - query(st-1); } };

int main(){
	ifstream f("distincte.in");
	ofstream g("distincte.out");

	int n, k, m;
	f >> n >> k >> m;

	vector<int> v(n);
	for(auto& x : v){
		f >> x;
		--x; }

	struct query{ int right, ind; };

	vector<long long> rez(m);
	vector<vector<query>> qs(n);
	for(int i = 0, st, dr; i < m; ++i){
		f >> st >> dr;
		qs[st-1].push_back((query){dr-1, i}); }

	vector<int> next(n, n+1), first_of(k, -1);
	{
		vector<int> next_for(k, n+1);
		for(int i = n-1; i >= 0; --i){
			next[i] = next_for[v[i]];
			next_for[v[i]] = i; } }
	for(int i = 0; i < n; ++i){
		if(first_of[v[i]] == -1){
			first_of[v[i]] = i; } }

	aib a(n);

	for(int i = 0; i < k; ++i){
		a.update(first_of[i], i+1); }
	for(int st = 0; st < n; ++st){
		for(const auto q : qs[st]){
			rez[q.ind] = a.query(st, q.right); }
		if(next[st] < n){
			a.update(next[st], v[next[st]]+1); } }

	for(const auto x : rez){
		g << x << '\n'; }
	return 0; }