C++ :

#define MAXN 100010UL

#include <cstdio>
#include <cmath>
#include <algorithm>

struct Query{
	int l,r,id;
	inline void in(int pid){scanf("%d%d",&l,&r);id=pid;return;}
};

Query p[MAXN];

int Ans[MAXN],c[MAXN],n,m,e,blocks,block[MAXN],Ans_now,ex[MAXN],L,R;

inline bool comp(Query a,Query b){
	return block[a.l]==block[b.l]?(a.r<b.r):(a.l<b.l);
}

inline void Update(int k,int add){
	k=c[k];
	if(add==1){
		if(ex[k]==1) Ans_now++;
		ex[k]++;
	}
	else{
		if(ex[k]==2) Ans_now--;
		ex[k]--;
	}
	return;
}

int main(){
	scanf("%d%d%d",&n,&e,&m);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=m;i++) p[i].in(i);
	blocks=(int)sqrt(n+0.5);
	for(int i=1;i<=n;i++) block[i]=(i-1)/blocks;
	std::sort(p+1,p+m+1,comp);
	L=p[1].l,R=p[1].r;
	for(int i=L;i<=R;i++) Update(i,1);
	Ans[p[1].id]=Ans_now;
	for(int i=2;i<=m;i++){
		while(R<p[i].r) R++,Update(R,1);
		while(L>p[i].l) L--,Update(L,1);
		while(R>p[i].r) Update(R,-1),R--;
		while(L<p[i].l) Update(L,-1),L++;
		Ans[p[i].id]=Ans_now;
	}
	for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);
	return 0;
}