#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,c,m;
int a[N],b[N],ans[N];
struct node{
	int l,r,id;
	bool operator <(const node &t) const{
		if(l==t.l) return r<t.r;
		return l<t.l;
	}
}q[N];
int nx=1,ny=0,sum;
inline void m1(int x,int y){
	for(int i=nx;i<x;i++){
		if(b[a[i]]==2){
			sum--;
		}
		b[a[i]]--;
	}
	for(int i=ny+1;i<=y;i++){
		if(b[a[i]]==1){
			sum++;
		}
		b[a[i]]++;
	}
}
inline void m2(int x,int y){
	for(int i=nx;i<x;i++){
		if(b[a[i]]==2){
			sum--;
		}
		b[a[i]]--;
	}
	for(int i=ny;i>y;i--){
		if(b[a[i]]==2){
			sum--;
		}
		b[a[i]]--;
	}	
}
inline void md(){
	for(int i=1;i<=m;i++){
		int ll=q[i].l,rr=q[i].r;
		if(rr<ny){
			m2(ll,rr);
		}
		else{
			m1(ll,rr);
		}
		nx=ll,ny=rr;
		ans[q[i].id]=sum;
	}
}
inline void read(int &x){
	int sum=0;
	char c;
	c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	}
	x=sum;
}
inline void write(int x){
	if(x/10) write(x/10);
	putchar(x%10+'0');
}
int main(){
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
	read(n);
	read(c);
	read(m);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		read(x);
		read(y);
		q[i]={x,y,i};
	}
	sort(q+1,q+1+m);
	md();
	for(int i=1;i<=m;i++){
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}