#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 200010

int n,k,m,i,j;
int v[nmax],kk[nmax],urm[nmax],a[nmax],b[nmax],ord[nmax],c[nmax];
int arb[2*nmax],st[2*nmax],en[2*nmax];

int fc(const void *x,const void *y)
{
	return a[*(int*)x]-a[*(int*)y];
}

void add(int x,int st1,int en1,int pos)
{
	if ((st[pos]>=st1)&&(en[pos]<=en1))
	{
		arb[pos]+=x;
		return;
	}
	if (st[pos]<st1)
	{
		if (st[pos*2+1]<=st1)
			add(x,st1,en1,pos*2+1);
		else
		{
			add(x,st1,en1,pos*2);
			if (en1>en[pos*2])
				add(x,st1,en1,pos*2+1);
		}
	}
	else
	{
		add(x,st1,en1,pos*2);
		if (en1>en[pos*2])
			add(x,st1,en1,pos*2+1);
	}
}

int query(int x)
{
	int ret=0,pos=1;
	while (st[pos]!=en[pos])
	{
		ret+=arb[pos];
		if (x>=st[pos*2+1])
			pos=pos*2+1;
		else
			pos=pos*2;
	}
	ret+=arb[pos];

	return ret;
}

void makearb(int pos,int st1,int en1)
{
	st[pos]=st1,en[pos]=en1;
	if (st1!=en1)
	{
		makearb(pos*2,st1,(st1+en1)/2);
		makearb(pos*2+1,(st1+en1)/2+1,en1);
	}
}

int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);

	scanf("%d%d%d",&n,&k,&m);
	for (i=1;i<=n;i++)
		scanf("%d",v+i);
	for (i=1;i<=k;i++)
		kk[i]=n+1;
	for (i=n;i>0;i--)
		urm[i]=kk[v[i]],kk[v[i]]=i;
	for (i=0;i<m;i++)
		scanf("%d%d",a+i,b+i),ord[i]=i;
	qsort((void*)ord,m,sizeof(ord[0]),fc);

	makearb(1,1,n);

	j=m-1;
	for (i=n;i>0;i--)
	{
		add(v[i],i,urm[i]-1,1);
		while (a[ord[j]]==i)
		{
			c[ord[j]]=query(b[ord[j]]);
			--j;
		}
	}

	for (i=0;i<m;i++)
		printf("%d\n",c[i]);

	return 0;
}