#include <stdio.h>
int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	int n,k,m,i,j,r,r1,verif,init,l;
	int a[100001],b[100001],par1[100000],par2[100000],suma[100000],gasit;
	scanf("%d%d%d",&n,&k,&m);
	for (i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for (j=1; j<=m; j++)
	{
		scanf("%d%d",&par1[j],&par2[j]);
		gasit=0;
		for (l=1; l<j; l++)
			if (par1[j]<=par1[l] && par2[j]>=par2[l])
			{
				suma[j]=suma[l];
				printf("%d\n",suma[j]);
				break;
				gasit=1;
			}
		if (gasit==0)
		{
		suma[j]=k*(k+1)/2;
		r=0;
		for (init=1; init<=k; init++)
		{	
			verif=0;
			for (i=par1[j]; i<=par2[j]; i++)
				if (a[i]==init)
				{
					verif=1;
					break;
				}
			if (verif==0)
				b[++r]=init;
		}
		for (r1=1; r1<=r; r1++)
			suma[j]-=b[r1];
		printf("%d\n",suma[j]);
		}
	}
	return 0;
}