#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,c,t[N],len,a[N];
struct que{
	int l,r,id;
}q[N];
bool cmp(que x,que y){
	if(x.l/len==y.l/len) return x.r<y.r;
	return x.l<y.l;
}
int res[N];
int main(){
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
	scanf("%d%d%d",&n,&c,&m); len=sqrt(n);
	for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
	for(int i = 1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int L=0,R=0,ans=0;
	for(int i = 1;i<=m;i++){
		while(L<q[i].l){
			t[a[L]]--;
			if(t[a[L]]==1) ans--;
			L++;
		}
		while(L>q[i].l){
			L--;
			t[a[L]]++;
			if(t[a[L]]==2) ans++;
		}
		while(R<q[i].r){
			R++;
			t[a[R]]++;
			if(t[a[R]]==2) ans++;
		}
		while(R>q[i].r){
			t[a[R]]--;
			if(t[a[R]]==1) ans--;
			R--;
		}
		res[q[i].id]=ans;
	}
	for(int i = 1;i<=m;i++)
	printf("%d\n",res[i]);
	return 0;
}