#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5*1e4;
struct node{
	int l,r,pos;
}q[N];
ll now=0;
ll ans[N];
int n,m,k;
int a[N];
int b[N];
int block;
bool cmp(node &a,node &b){
	if((a.l-1)/block==(b.l-1)/block) return a.r<b.r;
	return a.l/block<b.l/block;
}
void add(int t){
	now+=2*b[t]+1;
	b[t]++;
}
void del(int t){
	now-=2*b[t]-1;
	b[t]--;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].pos=i;
	}
	block=sqrt(n);
	int nl=1,nr=0;
	sort(q+1,q+1+m,cmp);
	for (int i=1;i<=m;i++){
		while(nl<q[i].l) del(a[nl]),nl++;
		while(nl>q[i].l) nl--,add(a[nl]);
		while(nr>q[i].r) del(a[nr]),nr--;
		while(nr<q[i].r) nr++,add(a[nr]);
		ans[q[i].pos]=now;
	}
	for (int i=1;i<=m;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}