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

auto pi_cmp = [](const pair<int, int>& a, const pair<int, int>& b){
	return a.first < b.first || (a.first == b.first && a.second < b.second); };

class arbint_simplu{
	int n;
	vector<pair<int, int>> vals;
	vector<int> buf;
	int& acc(const int poz){
		if(poz < n){
			return buf[poz]; }
		else{
			return vals[poz-n].second; } }
	const int& acc(const int poz)const{
		if(poz < n){
			return buf[poz]; }
		else{
			return vals[poz-n].second; } }
public:
	arbint_simplu(){}
	arbint_simplu(const vector<pair<int, int>>& v): n(v.size()), vals(v), buf(n){
		sort(begin(vals), end(vals), pi_cmp);
		for(int i = n-1; i > 0; --i){
			acc(i) = acc(2*i) + acc(2*i+1); } }
	arbint_simplu(const arbint_simplu& a, const arbint_simplu& b){
		vector<pair<int, int>> tmp;
		merge(begin(a.vals), end(a.vals), begin(b.vals), end(b.vals), back_inserter(tmp), pi_cmp);
		(*this) = arbint_simplu(tmp); }
	int query(int st, int dr)const{
		st = lower_bound(begin(vals), end(vals), make_pair(st, -100), pi_cmp) - begin(vals) + n,
		   dr = upper_bound(begin(vals), end(vals), make_pair(dr, 1000000000), pi_cmp) - begin(vals) + n;
		int rez = 0;
		for( ; st < dr; st /= 2, dr /= 2){
			if(st%2 == 1){
				rez += acc(st++); }
			if(dr%2 == 1){
				rez += acc(--dr); } }
		return rez; } };

class arbint_2d{
	int n;
	vector<arbint_simplu> buf;
public:
	arbint_2d(){}
	arbint_2d(const vector<pair<int, int>>& v): n(v.size()), buf(2*n){
		for(int i = 0; i < n; ++i){
			buf[i+n] = arbint_simplu(vector<pair<int, int>>({v[i]})); }
		for(int i = n-1; i > 0; --i){
			buf[i] = arbint_simplu(buf[2*i], buf[2*i+1]); } }
	int query(int st, int dr)const{
		int rez = 0;
		const int st_init = st;
		for(st += n, dr += n+1; st < dr; st /= 2, dr /= 2){
			if(st%2 == 1){
				rez += buf[st++].query(-1, st_init-1); }
			if(dr%2 == 1){
				rez += buf[--dr].query(-1, st_init-1); } }
		return rez; } };

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

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

	arbint_2d a2d;
	{
		vector<int> v(n), prev(k, -1), v2(n);

		for(auto& x : v){
			f >> x;
			--x; }
		for(int i = 0; i < n; ++i){
			v2[i] = prev[v[i]];
			prev[v[i]] = i; }

		vector<pair<int, int>> v3(n);
		for(int i = 0; i < n; ++i){
			v3[i] = make_pair(v2[i], v[i]+1); }
		a2d = arbint_2d(v3); }

	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		g << a2d.query(a-1, b-1) << '\n'; }
	return 0; }