p2706

#include<bits/stdc++.h>
using namespace std;

int n,m,k,a[50000<<3],sum,cnt[50000<<3];
int len,pos[50000<<3],ans[50000<<3];

struct node{
	int l,r,id;
}q[100000<<3];

bool cmp(node a,node b)
{
	if(pos[a.l]!=pos[b.l]) return a.l<b.l;
	else return a.r<b.r;
}

void add(int x)
{
	cnt[a[x]]++;
	sum+=cnt[a[x]]*cnt[a[x]]-(cnt[a[x]]-1)*(cnt[a[x]]-1);
}

void del(int x)
{
	cnt[a[x]]--;
	sum+=cnt[a[x]]*cnt[a[x]]-(cnt[a[x]]+1)*(cnt[a[x]]+1);
}

int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	len=sqrt(n);
	for(int i=1;i<=m;i++) {
		cin>>q[i].l>>q[i].r;q[i].id=i;
		
	}
    for(int i=1;i<=n;i++) pos[i]=(i-1)/len+1;;
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(q[i].l<l) add(--l);
		while(q[i].l>l) del(l++);
		while(q[i].r<r) add(++r);
		while(q[i].r>r) del(r--);
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}