#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;

int read(){
    int x = 0;
    int f = 1;
    char ch;
    while((ch = getchar()) < '0' || ch > '9'){
        if(ch == '-'){
            f = -1;
        }
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + (ch - '0');
        ch=getchar();
    } 
    return x * f;
}

const int MAXN = 1e6;
const int MAXM = 1e6;
const int MAXV = 1e6;
const int LEN = 1000;

struct QUESTION {
	int l, r;
	int ans;
	int id;
} ques[MAXM + 10];

bool cmp1(QUESTION x, QUESTION y) {
	if (x.l / LEN == y.l / LEN) {
		return x.r < y.r;
	}
	return x.l < y.l;
}

bool cmp2(QUESTION x, QUESTION y) {
	return x.id < y.id;
}

int n, c, m;
int a[MAXN + 10], t[MAXV + 10];

int main() {
	freopen("1flower.in", "r", stdin);
	freopen("1flower.out", "w", stdout);
	scanf("%d %d %d", &n, &c, &m);
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
	}
	for (int i = 1; i <= m; ++i) {
        ques[i].l = read(), ques[i].r = read();
		ques[i].id = i;
	}
	
	sort(ques + 1, ques + m + 1, cmp1);
	int nl = ques[1].l, nr = ques[1].r;
	for (int i = nl; i <= nr; ++i) {
		t[a[i]]++;
		if (t[a[i]] == 2) ques[1].ans++;
	}
	for (int i = 2; i <= m; ++i) {
		ques[i].ans = ques[i - 1].ans;
		while (nl < ques[i].l) {
			t[a[nl]]--;
			if (t[a[nl]] == 1) ques[i].ans--;
			nl++;
		}
		while (nl > ques[i].l) {
			nl--;
			t[a[nl]]++;
			if (t[a[nl]] == 2) ques[i].ans++;
		}
		while (nr < ques[i].r) {
			nr++;
			t[a[nr]]++;
			if (t[a[nr]] == 2) ques[i].ans++;
		}
		while (nr > ques[i].r) {
			t[a[nr]]--;
			if (t[a[nr]] == 1) ques[i].ans--;
			nr--;
		}
	}
	
	sort(ques + 1, ques + m + 1, cmp2);
	for (int i = 1; i <= m; ++i) {
		printf("%d\n", ques[i].ans);
	}
	return 0;
}