#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#include<math.h>
using namespace std;
int res=0,n,m,k,block[50010],cnt[50010];
struct az {
	int zhi,block;
};
az a[50010];
struct az2 {
	int l,r,wz;
};
az2 b[50010];
bool cmp(az2 a,az2 b) {
	if(block[a.l]==block[b.l])
		return a.r<b.r;
	else
		return block[a.l]<block[b.l];
}
void op1(int wzz) {
	cnt[a[wzz].zhi]++;
	int zh=cnt[a[wzz].zhi];
	res+=zh*zh-(zh-1)*(zh-1);
}
void op2(int wzz) {
	cnt[a[wzz].zhi]--;
	int zh=cnt[a[wzz].zhi];
	res+=zh*zh-(zh+1)*(zh+1);
//	res-=a[wz].zhi*a[wz].zhi;
}
int main() {
	cin>>n>>m>>k;
	int size=sqrt(n),i;
	for(i=1; i<=n; i++) {
		cin>>a[i].zhi;
//		a[i].wz=i;
		a[i].block=i/size;
	}
	for(i=1; i<=m; i++) {
		cin>>b[i].l>>b[i].r;
		b[i].wz=i;
//		b[i].block=i/size;
	}
	int result[50010];
	sort(b+1,b+m+1,cmp);
	int left=1,right=0;
	for(i=1; i<=m; i++) {
		while(left<b[i].l)op1(left++);
		while(left>b[i].l)op2(--left);
		while(right<b[i].r)op1(++right);
		while(right>b[i].r)op2(right--);
		result[b[i].wz]=res;
//		cout<<res<<" ";
//		cout<<res<<endl;
	}
	for(i=1; i<=m; i++)
		cout<<result[i]<<endl;
	return 0;
}