#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
vector<int> task[N],tasid[N];
vector<int> nums[N];
int len[N];
int n,c,m;
int a[N],tj[N];
int tre[N];
inline void upd(int p,int v){
	while(p<=n){
		tre[p]+=v;
		p+=(p&(-p));
	}
}
inline int que(int p){
	int ans=0;
	while(p){
		ans+=tre[p];
		p-=(p&(-p));
	}
	return ans;
}
int output[N];
int all;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>c>>m;
	for(int i=1;i<=n;i++)cin>>a[i],nums[a[i]].push_back(i);
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l >>r;
		task[r].push_back(l);
		tasid[r].push_back(i);
	}
	for(int i=1;i<=n;i++){
		len[a[i]]++;
		if(len[a[i]]==2)upd(nums[a[i]][0],1),all++;
		if(len[a[i]]>2)upd(nums[a[i]][len[a[i]]-3],-1),upd(nums[a[i]][len[a[i]]-2],1);
		
		for(int j=0;j<task[i].size();j++)output[tasid[i][j]]=all-que(task[i][j]-1);
		
	}
	for(int i=1;i<=m;i++)cout<<output[i]<<"\n";
	return 0;
}