#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int len,n,m,a[M],belong[M],sum,ans[M],cnt,l[M],r[M],c[M];
void fun() {
	len=sqrt(n),cnt=(n-1)/len+1;
	for(int i=1; i<=cnt; ++i)l[i]=r[i-1]+1,r[i]=len*i;
	r[cnt]=n;
	for(int i=1; i<=cnt; ++i)
		for(int j=l[i]; j<=r[i]; ++j)belong[j]=i;
}
struct dian {
	int l,r,id;
} f[M];
bool operator<(dian a,dian b) {
	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void add(int x) {
	sum-=c[a[x]]*c[a[x]];
	c[a[x]]++;
	sum+=c[a[x]]*c[a[x]];
}
void dele(int x) {
	sum-=c[a[x]]*c[a[x]];
	c[a[x]]--;
	sum+=c[a[x]]*c[a[x]];
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int k;
	cin>>n>>m>>k;
	int l=1,r=0;
	for(int i=1; i<=n; ++i)cin>>a[i];
	fun();
	for(int i=1; i<=m; ++i)cin>>f[i].l>>f[i].r,f[i].id=i;
	sort(f+1,f+1+m);
	for(int i=1; i<=m; ++i) {
		while(l>f[i].l)add(--l);
		while(r<f[i].r)add(++r);
		while(l<f[i].l)dele(l++);
		while(r>f[i].r)dele(r--);
		ans[f[i].id]=sum;
	}
	for(int i=1; i<=m; ++i)cout<<ans[i]<<'\n';
	return 0;
}