#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long INF64=(long long)(1e18);
const int N=2000050;
int a[N],s[N],vis[N],lvis[N],ans[N],n;
struct node{
	int l,r,id;
}b[N];
inline void read(int &x){
	char ch=getchar();int f=1;x=0;
	while(!isdigit(ch) && ch^'-') ch=getchar();
	if(ch=='-') f=-1,ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}
inline bool cmp(node a,node b){
	return a.r<b.r;
}
inline int lowbit(int x){
	return x&(-x);
}
inline void add(int x,int k){
	while(x<=n)s[x]+=k,x+=lowbit(x);
}
inline int sum(int x){
	int t=0;
	while(x)t+=s[x],x-=lowbit(x);
	return t;
}
int main(){
    int c,m;
    read(n),read(c),read(m);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
    	read(b[i].l),read(b[i].r);
    	b[i].id=i;
	}
    sort(b+1,b+1+m,cmp);
    int now=1;
    for(int i=1;i<=m;i++){
    	for(int j=now;j<=b[i].r;j++){
    		if(lvis[a[j]]){
    			add(lvis[a[j]],-1);
    			add(vis[a[j]],1);
    		   	lvis[a[j]]=vis[a[j]];
    			vis[a[j]]=j;
			}
    		else if(vis[a[j]]){
    			lvis[a[j]]=vis[a[j]];
    			vis[a[j]]=j;
    			add(lvis[a[j]],1);
			}
    		else {
    			vis[a[j]]=j;
			}
		}
		now=b[i].r+1;
		ans[b[i].id]=sum(b[i].r)-sum(b[i].l-1);
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
	return 0;
}