#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

int const xn=5e4+;

int n,m,k,cnt[xn],d[xn],blk[xn],a[xn];

ll sum,ans[xn];

struct N{int l,r,id;}q[xn];

bool cmp(N x,N y){return blk[x.l]==blk[y.l]?x.r<y.r:blk[x.l]<blk[y.l];}

int rd()

{

  int ret=,f=; char ch=getchar();

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

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

void add(int ps)

{

  int x=a[ps];

  sum-=(ll)cnt[x]*cnt[x];

  cnt[x]++;

  sum+=(ll)cnt[x]*cnt[x];

}

void del(int ps)

{

  int x=a[ps];

  sum-=(ll)cnt[x]*cnt[x];

  cnt[x]--;

  sum+=(ll)cnt[x]*cnt[x];

}

int main()

{

  n=rd(); m=rd(); k=rd(); int bs=sqrt(n);

  for(int i=;i<=n;i++)a[i]=rd(),blk[i]=(i-)/bs+;

  for(int i=;i<=m;i++)q[i].l=rd(),q[i].r=rd(),q[i].id=i;

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

  for(int i=,l=,r=;i<=m;i++)

    {

      int ql=q[i].l,qr=q[i].r;

      while(l<ql)del(l),l++;

      while(l>ql)l--,add(l);

      while(r<qr)r++,add(r);

      while(r>qr)del(r),r--;

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

    }

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

  return ;

}