#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
struct md{
	int l,r,id;
}www[50005];
ll n,m,k,a[50005],tong[50005],ans[50005],block,c=0;
inline bool cmp(md a,md b){
	if((a.l-1)/block==(b.l-1)/block) return a.r<b.r;
	return (a.l)/block<(b.l)/block;
}
inline void add(ll x){
	c+=2*tong[x]+1;
	tong[x]++;
	return ;
}
inline void dele(ll x){
	c-=2*tong[x]-1;
	tong[x]--;
	return ;
}
int main(){
	cin >>n>>m>>k;
	ll block=sqrt(n),left,right,ans1=1,ans2=0;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	for(int i=1;i<=m;i++){
		cin >>www[i].l>>www[i].r;
		www[i].id=i;
	}
	sort(www+1,www+1+m,cmp);
	for(int i=1;i<=m;i++){
		left=www[i].l;
		right=www[i].r;
		while(ans1>left) ans1--,add(a[ans1]);
		while(ans2<right) ans2++,add(a[ans2]);
		while(ans1<left) dele(a[ans1]),ans1++;
		while(ans2>right) dele(a[ans2]),ans2--;
		ans[www[i].id]=c;
	}
	for(int i=1;i<=m;i++){
		cout <<ans[i]<<endl;
	}
	return 0;
}

一直RE 求求找下错