void mult(int x,int a[])
{
    int k=0;
    for(int i=1;i<=a[0];i++)
    {
        int tmp=a[i]*x+k;
        a[i]=tmp%10;
        k=tmp/10;
    }
    while(k)a[++a[0]]=k%10,k/=10;
}

void getpri()
{
    for(int i=2;i<=10000;i++)
    {
        if(!vis[i])pri[++tot]=i;
        for(int j=1;j<=tot;j++)
        {
            if(i*pri[j]>10000)break;
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}

void getprime()
{
    for(int i=2;i<=2*n;i++)
    {
        if(!vis[i])pri[++tot]=i,res[i]=tot;
        for(int j=1;j<=tot;j++)
        {
            if(i*pri[j]>2*n)break;
            vis[i*pri[j]]=1;res[i*pri[j]]=j;
            if(i%pri[j]==0)break;
        }
    }
}
void divi(int x,int val)
{
    while(x!=1)bu[res[x]]+=val,x/=pri[res[x]];    
}

void Minus(int a[],int b[])
{
    int j=1,x=0;
    while(j<=a[0]||j<=b[0])
    {
        if(a[j]<b[j])
        {
            a[j]+=10;
            a[j+1]--;
        }
        ans[j]=a[j]-b[j];
        j++;
    }
    int k=j;
    while(ans[k]==0&&k>1)k--;
    ans[0]=k;
}

void add(int m[],int n[])
{
    int j=1,x=0;
    while(j<=m[0]||j<=n[0])
    {
        c[j]=m[j]+n[j]+x;
        x=c[j]/10;
        c[j]%=10;
        j++;
    }
    c[j]=x;
    if(c[j]==0)j--;
    for(int i=j;i>=1;i--)
    cout<<c[i];
}

void dx(int m[],int n[])
{
    for(int i=1;i<=m[0];i++)
    {
        int x=0;
        for(int j=1;j<=n[0];j++)
        {
            c[i+j-1]=m[i]*n[j]+x+c[i+j-1];
            x=c[i+j-1]/10;
            c[i+j-1]%=10;
        }
        c[i+n[0]]=x;
    }
    c[0]=m[0]+n[0];
    while(c[c[0]]==0&&c[0]>1)c[0]--;
    for(int i=c[0];i>=1;i--)cout<<c[i];
}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=50005;
int n,m,k;
int cnt[N],a[N],size,p,ans[N];
struct query
{
    int l,r,id,bel;
}q[N];
int cmp(query x,query y)
{
    return x.bel!=y.bel?x.l<y.l:((x.bel&1)?x.r<y.r:x.r>y.r); 
}
int read()
{
    int x=0;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘)ch=getchar();
    while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();
    return x;
}

int main()
{
    n=read();m=read();k=read();
    size=(int)sqrt(n);
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i,q[i].bel=(q[i].l-1)/size+1;
    sort(q+1,q+m+1,cmp);
    /*for(int i=1;i<=m;i++)
        cout<<q[i].id<<‘ ‘<<q[i].l<<‘ ‘<<q[i].r<<‘ ‘<<endl;*/
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        int ql=q[i].l,qr=q[i].r;
        while(l<ql)cnt[a[l]]--,p-=2*cnt[a[l]]+1,l++;
        while(l>ql)l--,cnt[a[l]]++,p+=2*cnt[a[l]]-1;
        while(r<qr)r++,cnt[a[r]]++,p+=2*cnt[a[r]]-1;
        while(r>qr)cnt[a[r]]--,p-=2*cnt[a[r]]+1,r--;
        ans[q[i].id]=p;
    }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<endl;
    return 0;
}