本人萌新，初学OI,莫队写挂了QWQ

#include<bits/stdc++.h>
#define MAXN 50010 
using namespace std;
int n,i,j,ans=0,_m,l,r,m,L,R,k;
struct _Modui{int l,r,wz;};
_Modui a[MAXN];
int col[MAXN],col_cnt[MAXN];
int ans_arr[MAXN];
namespace Fastio{
	int read(){
		int x=0;char c=getchar();
		while(!isdigit(c)) c=getchar();
		while(isdigit(c)) {x=x*10+c-48;c=getchar();}
		return x;
	}
	void write(int x){
		if(x/10>0) write(x/10);
		putchar(x%10+48);
		return;
	}
}
using namespace Fastio; 
bool cmp(_Modui a,_Modui b){
	if(a.l==b.l) return a.r<b.r;
	else return a.l<b.l;
} 
void add(int x){
	col_cnt[col[x]]++;
	int k=col_cnt[col[x]];
	ans+=(k*k-(k-1)*(k-1));
}   
void del(int x){
	col_cnt[col[x]]--;
	int k=col_cnt[col[x]];
	ans-=((k+1)*(k+1)-k*k);
}
int main(){        
	n=read();_m=read();k=read();
	for(i=1;i<=n;i++){
		col[i]=read();
	}
	for(i=1;i<=_m;i++){
		a[i].wz=i;a[i].l=read();a[i].r=read();
	}
	sort(a+1,a+_m+1,cmp);
	l=0;r=1;
	for(i=1;i<_m;i++){
		int L=a[i].l;int R=a[i].r;
		while(l<L) add(l++);
		while(l>L) del(--l);
		while(r<R) add(++r);
		while(r>R) del(r--);
		ans_arr[a[i].wz]=ans;
	}
	for(i=1;i<=_m;i++){
		write(ans_arr[i]);
		printf("\n");
	}
	return 0;
}