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

using namespace std;

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

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

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

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

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

long long querry(long x)
{
    long long 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("%ld %ld %ld", &n, &k, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%ld", &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("%ld %ld", &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;
    p2=1;

    for(i=1; i<=n; i++)
    {
        while(a[pa[p1]]==i && p1<=m)
        {
            va[pa[p1]]=(long long)querry(n+1)-querry(b[pa[p1]]);
    //        printf("%d ", b[pa[p1]]);
            p1++;
        }
        update(v[i], p[i]);
        while(b[pb[p2]]==i && p2<=m)
        {
            vb[pb[p2]]=(long long)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("%lld\n", vb[i]-va[i]);
    return 0;
}