#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y,z;
}e[3000010];
bool cmp(node A,node B){
	return A.y<B.y;
}
long long n,a[3000010],l[3000010],b[3000010],c,m,ans[3000010],num[3000010];
void add(long long x,long long y){
	if(x==0)
	return;
	for(;x<=n;x+=x&-x){
		num[x]+=y;
	}
}
long long ask(long long x){
	long long res=0;
	for(;x;x-=x&-x){
		res+=num[x];
	}
	return res;
}
int main(){
	freopen("1flower.in","r",stdin);
			freopen("1flower.out","w",stdout);
	cin>>n>>c>>m;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
		l[i]=b[a[i]],b[a[i]]=i;
	}
	for(long long i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y;
		e[i].z=i;
	}
	sort(e+1,e+m+1,cmp);
	for(long long i=1,j=1;i<=n;i++){
	    add(l[l[i]],-1),add(l[i],1);
		while(e[j].y==i&&j<=m){
			ans[e[j].z]=ask(e[j].y)-ask(e[j].x-1);
			j++;
			
		}
	}
	for(long long i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}