#include<bits/stdc++.h>
using namespace std;
inline int re()
{
	int f=1,num=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
	return num*f;
}
const int N=1000010;
int n,c,m,k;
int col[N],t[N],res[N];
struct query
{
	int l,r,bi,kk;
	bool operator <(const query &b) const
	{
		if(kk==b.kk)
		{
			if((kk)%2) return r<b.r;
			return r>b.r;
		}
		return kk<b.kk;
	}
}qs[N];
int ans;
void add(int x)
{
	t[col[x]]++;
	if(t[col[x]]==2) ans++;
}
void del(int x)
{
	t[col[x]]--;
	if(t[col[x]]==1) ans--;
}
int main()
{
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
	n=re();c=re();m=re();k=1000;
	for(int i=1;i<=n;i++) col[i]=re();
	for(int i=1;i<=m;i++) qs[i].l=re(),qs[i].r=re(),qs[i].bi=i,qs[i].kk=qs[i].l/k;
	sort(qs+1,qs+1);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		while(l>qs[i].l) add(--l);
		while(r<qs[i].r) add(++r);
		while(l<qs[i].l) del(l++);
		while(r>qs[i].r) del(r--);
		res[qs[i].bi]=ans;
	}
	for(int i=1;i<=m;i++) printf("%d\n",res[i]);
	return 0;
}