#include<cstdio>
#include<algorithm>
using namespace std;
const int nmax=100000;
struct nod
{
    long long sum;
    nod * fiust,*fiudr;
    nod()
    {
        sum=0;
        fiust=fiudr=NULL;
    };
};
struct sp
{
    long long ans;
    int st,dr,po;
} inter[nmax+5];

int in[nmax+5],lv[nmax+5],last[nmax+5];

void prop(nod * rot)
{
    if(rot->fiust==NULL)
        rot->fiust=new nod();
    if(rot->fiudr==NULL)
        rot->fiudr=new nod();
}

void update(nod *rot,int st,int dr,int val,int p)
{
    int mi=(st+dr)/2;
    rot->sum+=val;
    if(st==dr)
        return ;
    prop(rot);
    if(p<=mi)
        update(rot->fiust,st,mi,val,p);
    else
        update(rot->fiudr,mi+1,dr,val,p);
}
bool cmp(sp a1,sp a2)
{
    return a1.dr<a2.dr;
}
long long query(nod * rot,int le,int ri,int st,int dr)
{
    if(st==le && dr==ri)
    {
        return rot->sum;

    }
    int mi=(le+ri)/2;
    prop(rot);
    if(dr<=mi)
        return query(rot->fiust,le,mi,st,dr);
    else
        if(st>mi)
        return query(rot->fiudr,mi+1,ri,st,dr);
    else
        return query(rot->fiust,le,mi,st,mi)+query(rot->fiudr,mi+1,ri,mi+1,dr);
}
bool ini(sp a1,sp a2)
{
    return a1.po<a2.po;
}
int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    int n,m,k,i,j;
    nod * root=new nod();
    scanf("%d%d%d",&n,&k,&m);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&in[i]);
        last[i]=lv[in[i]];
        lv[in[i]]=i;
    }
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&inter[i].st,&inter[i].dr);
        inter[i].po=i;
    }
    sort(inter+1,inter+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        for(j=inter[i-1].dr+1;j<=inter[i].dr;j++)
        {
            update(root,1,n,in[j],j);
            if(last[j]!=0)
            update(root,1,n,-in[j],last[j]);
        }
        inter[i].ans=query(root,1,n,inter[i].st,inter[i].dr);

    }
    sort(inter+1,inter+m+1,ini);
    for(i=1;i<=m;i++)
        printf("%lld\n",inter[i].ans);
    return 0;
}