#include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define MAXN 50010

 struct node

 {

     int l,r,id;

 }q[MAXN];

 LL ans[MAXN];

 int C[MAXN],pos[MAXN],tot[MAXN];

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 bool cmp(node a,node b)

 {

     if(pos[a.l]==pos[b.l])return a.r<b.r;

     return a.l<b.l;

 }

 int main()

 {

     int n,m,k,block,i,L,R;

     LL res;

     n=read();m=read();k=read();

     for(i=;i<=n;i++)C[i]=read();

     block=(int)sqrt(n);

     for(i=;i<=n;i++)pos[i]=(i-)/block+;

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

     {

         q[i].l=read();q[i].r=read();

         q[i].id=i;

     }

     sort(q+,q+m+,cmp);

     L=;R=;res=;

     memset(tot,,sizeof(tot));

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

     {

         while(L<q[i].l)

         {

             res-=tot[C[L]]*tot[C[L]];

             tot[C[L]]--;

             res+=tot[C[L]]*tot[C[L]];

             L++;

         }

         while(L>q[i].l)

         {

             L--;

             res-=tot[C[L]]*tot[C[L]];

             tot[C[L]]++;

             res+=tot[C[L]]*tot[C[L]];

         }

         while(R<q[i].r)

         {

             R++;

             res-=tot[C[R]]*tot[C[R]];

             tot[C[R]]++;

             res+=tot[C[R]]*tot[C[R]];

         }

         while(R>q[i].r)

         {

             res-=tot[C[R]]*tot[C[R]];

             tot[C[R]]--;

             res+=tot[C[R]]*tot[C[R]];

             R--;

         }

         ans[q[i].id]=res;

     }

     for(i=;i<=m;i++)printf("%lld\n",ans[i]);

     fclose(stdin);

     fclose(stdout);

     return ;

 }