here

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int m,t,n,a[10000001],p[10000001],s,c[10000001];
struct yyy
{
  int l,r,id;
} q[10000001];
bool cmp(yyy a,yyy b)
{
  if (a.l / t == b.l / t) return a.r < b.r;
  else return a.l / t < b.l / t;
}
void add(int id)
{
  s -= c[a[id]] * c[a[id]];
  ++c[a[id]];
  s += c[a[id]] * c[a[id]];
}
void del(int id)
{
  s -= c[a[id]] * c[a[id]];
  --c[a[id]];
  s += c[a[id]] * c[a[id]];
}
signed main()
{
  int pp;
  cin>>n>>m>>pp;
  for(int i = 1; i <= n; i++) cin>>a[i];
  for(int i = 1; i <= m; i++)
  {
    cin>>q[i].l>>q[i].r;
    q[i].id = i;
  }
  t = sqrt(n);
  sort(q + 1,q + 1 + m,cmp);
  int L = 1,R = 0;
  for(int i = 1; i <= m; i++)
  {
    while(R < q[i].r) add(a[++R]);
    while(L > q[i].l) add(a[--L]);
    while(R > q[i].r) del(a[R--]);
    while(L < q[i].l) del(a[L++]);
    p[q[i].id] = s;
  }
  for(int i = 1; i <= m; i++) cout<<p[i]<<'\n';
  return 0;
}