#include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 int a[N],vis[N],ans,tot[N];

 int block;

 struct node{

     int l,r;

     int id;

 }q[N];

 bool cmp(node aa,node bb){

     if(aa.l/block==bb.l/block) return aa.r<bb.r;

     return aa.l/block<bb.l/block;

 }

 void add(int pos){

     ans-=vis[a[pos]]*vis[a[pos]];

     vis[a[pos]]++;

     ans+=vis[a[pos]]*vis[a[pos]];

 }

 void del(int pos){

     ans-=vis[a[pos]]*vis[a[pos]];

     vis[a[pos]]--;

     ans+=vis[a[pos]]*vis[a[pos]];

 }

 int main(){

     int n,m,k;

     scanf("%d%d%d",&n,&m,&k);

     block=sqrt(n);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

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

         scanf("%d%d",&q[i].l,&q[i].r);

         q[i].id=i;

     }

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

     int L=,R=;

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

         while(L>q[i].l){

             L--;

             add(L);

         }

         while(L<q[i].l){

             del(L);

             L++;

         }

         while(R<q[i].r){

             R++;

             add(R);

         }

         while(R>q[i].r){

             del(R);

             R--;

         }

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

     }

     for(int i=;i<=m;i++) printf("%d\n",tot[i]);

     return ;

 }