#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 1000010
#define qmod(x) (x>mod?x-mod:x)
// By flyfreemrn
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll n,m,c;
struct node_bit{
	ll s[MAXN];
	ll lowbit(ll x){
		return x&(-x);
	}
	void modify(ll x,ll val){
		while(x<=n){
			s[x]+=val;
			x+=lowbit(x);
		}
	}
	ll query(ll x){
		ll res=0;
		while(x>0){
			res+=s[x];
			x-=lowbit(x);
		}
		return res;
	}
}bit;
struct node_qs{
	ll l,r,ans,id;
}qs[MAXN];
bool cmp(node_qs qsa,node_qs qsb){
	return qsa.r<qsb.r;
}
ll a[MAXN],pre[MAXN],t[MAXN],re_id[MAXN];
void insert(ll pos){
	pre[pos]=t[a[pos]];
	t[a[pos]]=pos;
	if(pre[pre[pos]])bit.modify(pre[pre[pos]],-1);
	if(pre[pos])bit.modify(pre[pos],1);
}
int main(){
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
	n=read(),c=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++)qs[i].l=read(),qs[i].r=read(),qs[i].id=i;
	sort(qs+1,qs+1+m,cmp);
	ll r=0;
	for(int i=1;i<=m;i++){
		re_id[qs[i].id]=i;
		while(r<qs[i].r)r++,insert(r);
		qs[i].ans=bit.query(qs[i].r)-bit.query(qs[i].l-1);
	}
	for(int i=1;i<=m;i++)cout<<qs[re_id[i]].ans<<endl;
	return 0;
}