rt

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
int n,m,k,a[50001],ans,cx[50001],sum[50001],t,l,r,pos[50001];
inline int read()
{
	int x=0,fh=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*fh;
}
struct WEN
{
	int x,y,id;
}q[50001];
bool cmp(WEN a,WEN b)
{
	if(pos[a.x]==pos[b.x])
	{
		return a.y<b.y;
	}
	return pos[a.x]<pos[b.x];
}
int ad(int x)
{
	cx[a[x]]++;
	ans+=cx[a[x]]*cx[a[x]]-(cx[a[x]]-1)*(cx[a[x]]-1);
}
int qu(int x)
{
	cx[a[x]]--;
	ans+=cx[a[x]]*cx[a[x]]-(cx[a[x]]+1)*(cx[a[x]]+1);
}
signed main()
{
//	freopen("P2709_1.in","r",stdin);
	n=read(),m=read(),k=read();
	t=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		pos[i]=i/t+1;
	}
	for(int i=1;i<=m;i++)
	{
		q[i].x=read(),q[i].y=read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].x) qu(l++);
		while(l>q[i].x) ad(--l);
		while(r<q[i].y) ad(++r);
		while(r>q[i].y) qu(r--);
		sum[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",sum[i]);
	}
	return 0;
}