#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int belong[N],ans[N],a[N],cnt[N];
struct Node{
  int l,r,id;
  bool operator<(const Node&rhs)const{
    return belong[l]<belong[rhs.l]||belong[l]!=belong[rhs.l]&&r<rhs.r;
  }
}z[N];
inline char nc(){
  static char buf[3000000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,3000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
  register char ch=nc();register int sum=0;
  while(!(ch>='0'&&ch<='9'))ch=nc();
  while(ch>='0'&&ch<='9')sum=(sum<<3)+(sum<<1)+(ch^48),ch=nc();
  return sum;
}
int main(){
  srand(time(0));
  register int n,c,m,res=0;
  n=read(),c=read(),m=read();
  for(register int i=1;i<=n;++i)a[i]=read();
  for(register int i=1;i<=m;++i)z[i].id=i;
  for(register int i=1;i<=m;++i)z[i].l=read(),z[i].r=read();
  // register int block=pow(n,0.66);
  register int block=sqrt(n);
  for(register int i=1;i<=n;++i)
    belong[i]=i/block+1;
  sort(z+1,z+m+1);
  register int l=1,r=0;
  for(register int i=1;i<=m;++i){
    while(l>z[i].l)res+=(++cnt[a[--l]]==2);
    while(r<z[i].r)res+=(++cnt[a[++r]]==2);
    while(l<z[i].l)res-=(--cnt[a[l++]]==1);
    while(r>z[i].r)res-=(--cnt[a[r--]]==1);
    ans[z[i].id]=res;
  }
  for(register int i=1;i<=m;++i)
    printf("%d\n",ans[i]);
  return 0;
}

TLE 100