#include <cstdio>
#include <algorithm>
#define MAXN 100000
#define zeros(x) (x&(-x))
struct Query{
   int l;
   int r;
   int poz;
};
Query Q[MAXN+1];
int aib[MAXN+1];
long long rez[MAXN+1];
struct Data{
   int l;
   int r;
   int val;
};
Data V[MAXN+1];
int last[MAXN+1];
int v[MAXN+1];
int n;
inline void update(int poz,int val){
    int i;
    for(i=poz;i<=n;i+=zeros(i))
      aib[i]+=val;
}
inline long long query(int poz){
   int i;
   long long ans=0;
   for(i=poz;i>0;i-=zeros(i))
     ans+=aib[i];
   return ans;
}
bool cmp1(Query a,Query b){
    return a.r<b.r;
}
bool cmp2(Data a,Data b){
    return a.r<b.r;
}
int main(){
   FILE*fi,*fout;
   int i,k,m,poz,j;
   fi=fopen("distincte.in" ,"r");
   fout=fopen("distincte.out" ,"w");
   fscanf(fi,"%d %d %d " ,&n,&k,&m);
   for(i=1;i<=n;i++)
     fscanf(fi,"%d " ,&v[i]);
   for(i=1;i<=n;i++){
      V[i].val=v[i];
      V[i].l=i;
      if(last[v[i]]<=i){
         j=i+1;
         while(j<=n&&v[j]!=v[i])
            j++;
         V[i].r=j;
         last[v[i]]=j;
      }
      else
         V[i].r=last[v[i]];
   }
   for(i=1;i<=m;i++){
      fscanf(fi,"%d %d " ,&Q[i].l,&Q[i].r);
      Q[i].poz=i;
   }
   std::sort(Q+1,Q+m+1,cmp1);
   std::sort(V+1,V+n+1,cmp2);
   poz=n;
   for(i=1;i<=m;i++){
      while(poz>0&&Q[i].r<V[poz].r){
         update(V[poz].l,V[poz].val);
         poz--;
      }
      rez[Q[i].poz]=query(Q[i].r)-query(Q[i].l-1);
   }
   for(i=1;i<=m;i++)
     fprintf(fout,"%lld\n" ,rez[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}