#include <cstdio>

 #include <algorithm>

 struct que

 {

     int l,r,id;

 } q[];

 bool operator<(que a,que b){return a.r<b.r;}

 int n,l[],an,c,m,o[],pre[],co[],ans[];

 void add(int a,int b)

 {

     while(a<=n)

         l[a]+=b,a+=a&-a;

 }

 int get(int a)

 {

     for(an=;a;a-=a&-a)

         an+=l[a];

     return an;

 }

 int main()

 {

     scanf("%d%d%d",&n,&c,&m);

     for(int i=;i<=n;i++)

         scanf("%d",&o[i]),pre[i]=co[o[i]],co[o[i]]=i;

     for(int i=;i<=m;i++)

         scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;

     std::sort(q+,q+m+);

     int rnow=;

     for(int i=;i<=m;i++)

     {

         while(rnow<q[i].r)

             if(pre[++rnow]>)

                 add(pre[pre[rnow]]+,),add(pre[rnow]+,-);

         ans[q[i].id]=get(q[i].l);

     }

     for(int i=;i<=m;i++)

         printf("%d\n",ans[i]);

     return ;

 }