#include <stdio.h>
#include <algorithm>

using namespace std;

long v[100100], aib[100100], p[100100], po[100100], pa[100100], pb[100100], a[100100], b[100100], va[100100], vb[100100];
long n, i, j, k, m, l, p1, p2;

inline int cmp1(int x, int y)
{
    return a[x]<a[y];
}

inline int cmp2(int x, int y)
{
    return b[x]<b[y];
}

long lsb(long x)
{
    return (x&(x-1))^x;
}

void update(int x, int y)
{
    while(y<=n+1)
    {
        aib[y]=aib[y]+x;
        y=y+lsb(y);
    }
}

int querry(int x)
{
    int s;
    s=0;
    while(x)
    {
        s=s+aib[x];
        x=x-lsb(x);
    }
    return s;
}


int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    
    scanf("%d %d %d", &n, &k, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &v[i]);
    }
    
    for(i=1; i<=k; i++)
    po[i]=n+1;
    
    for(i=n; i>0; i--)
    {
        p[i]=po[v[i]];
        po[v[i]]=i;
    }
    
    for(i=1; i<=m; i++)
    {
        scanf("%d %d", &a[i], &b[i]);
        pa[i]=i;
        pb[i]=i;
    }
    
    sort(pa+1, pa+m+1, cmp1);
    sort(pb+1, pb+m+1, cmp2);
    
    p1=1;
    while(a[pa[p1]]==1 && p1<=m)
    {
        p1++;
    }
    p2=1;
  //  printf("%d\n",p1);

    for(i=1; i<=n; i++)
    {
        update(v[i], p[i]);
        while(a[pa[p1]]==i+1 && p1<=m)
        {
            va[pa[p1]]=querry(n+1)-querry(b[pa[p1]]);
         //   printf("%d ", b[pa[p1]]);
            p1++;
        }
        while(b[pb[p2]]==i && p2<=m)
        {
            vb[pb[p2]]=querry(n+1)-querry(b[pb[p2]]);
            p2++;
        }
      //  for(j=1; j<=n+1; j++)
  //      {
   //        printf("%d ", aib[j]);
  //      }
  //      printf("\n"); 
    }
    for(i=1; i<=m; i++)
    printf("%d\n", vb[i]-va[i]);
    return 0;
}