#include <bits/stdc++.h> 
using namespace std;

struct node{
	int l,r,ps;
}t[2000010];

int l1[2000010],l2[2000010],c[2000010],a[2000010],ans[2000010];
int n,q,m;

bool cmp(node A,node B){
   return A.r<B.r;
}

void add(int x,int val){
    for(int i=x;i<=n;i+=(i&-i))c[i]+=val;
}

int query(int x){
    int ans=0;
    for(int i=x;i;i-=(i&-i))ans+=c[i];
    return ans;
}

int main(){
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout); 
    scanf("%d%d%d",&n,&q,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=m;++i){
       scanf("%d%d",&t[i].l,&t[i].r);
       t[i].ps=i;
    }
    sort(t+1,t+m+1,cmp);
    int j=1;
    for(int i=1;i<=m;++i){
    	for(;j<=t[i].r;++j){
           if(!l1[a[j]])l1[a[j]]=j;
           else {
           	  if(!l2[a[j]]){
           	  	add(l1[a[j]],1);
                l2[a[j]]=j;
           	  }else {
           	  	 add(l2[a[j]],1);
           	  	 add(l1[a[j]],-1);
           	  	 l1[a[j]]=l2[a[j]];
           	  	 l2[a[j]]=j;
           	  } 
           }
    	}
    	ans[t[i].ps]=query(t[i].r)-query(t[i].l-1);
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}