#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define RR register

#define N 1000010

using namespace std;

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int read()

{

	int x=0; char c=nc();

	while(!isdigit(c)) c=nc();

	while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=nc();

	return x;

}

struct Node

{

	int l,r,id,ans;

}q[N];

int nxt[N],tree[N],a[N],p[N],n;

inline bool cmp1(const Node &x,const Node &y)

{

	return x.l==y.l?x.r<y.r:x.l<y.l;

}

inline bool cmp2(const Node &x,const Node &y)

{

	return x.id<y.id;

}

inline int lowbit(int x) {return x&(-x);}

void update(int x,int val)

{

	for(RR int i=x;i<=n+1;i+=lowbit(i))

	{

		tree[i]+=val;

	}

}

int query(int x)

{

	int ans=0;

	for(RR int i=x;i>=1;i-=lowbit(i))

	{

		ans+=tree[i];

	}

	return ans;

}

int main()

{

	n=read();

	int mx=read(),m=read();

	for(RR int i=1;i<=n;i++) a[i]=read();

	for(RR int i=n;i>=1;i--)

	{

		nxt[i]=p[a[i]];

		p[a[i]]=i;

	}

	for(RR int i=1;i<=mx;i++)

	{

		if(p[i]&&nxt[p[i]]) update(nxt[p[i]],1);

	}

	for(RR int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;

	sort(q+1,q+m+1,cmp1);

	int l=1;

	for(RR int i=1;i<=m;i++)

	{

		while(l<q[i].l)

		{

			if(nxt[l]) update(nxt[l],-1);

			if(nxt[nxt[l]]) update(nxt[nxt[l]],1);

			l++;

		}

		q[i].ans=query(q[i].r)-query(q[i].l-1);

	}

	sort(q+1,q+m+1,cmp2);

	for(RR int i=1;i<=m;i++)

	{

		printf("%d\n",q[i].ans);

	}

	return 0;

}