rt，实在搞不下去了/kel

#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30) 
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 
#define y(x) id[x]
#define f(x) x/S
using namespace std;

const int inf=1e9;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
int read(){
	int res=0,fs=1; char c=getchar();
	while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
	while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
	return res*fs;
}
void print(int x){
    if(x<0) { putchar('-'); x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,cnt,m,a[1014141],ans,k,tmp,aw[1014141],id[1014141];
struct Q{
	int l,r,idx,ans;
}q[1014141];
char f[2020];

inline void write(register int x)
{
    register int tmp=x>0?x:-x,Cnt=0;
    if(x<0)putchar('-');
    while(tmp>0)f[Cnt++]=tmp%10+'0',tmp/=10;
    while(Cnt>0)putchar(f[--Cnt]);
    putchar('\n');
}
int S;
bool cmp(Q x,Q y){ 
	return ((y(x.l)^y(y.l))?x.l<y.l:((y(x.l)&1)?x.r<y.r:x.r>y.r));
} 
int t[1014141];
int main() { 
//	cin>>n;
	n=read();
	m=read();
	k=read(); 
	S=2135;
	for(reg i=1;i<=n;i++) id[i]=f(i);
	for(reg i=1;i<=n;i++) a[i]=read();
//	cin>>m; 
	for(reg i=1;i<=m;i++) {
		int t1,t2;
		t1=read(),t2=read();
		q[i]={t1,t2,i,0};
	}
	sort(q+1,q+m+1,cmp);
	reg l=1,r=0;
	for(reg i=1;i<=m;i++){
	    int st=q[i].l,ed=q[i].r;
		while(l<st) { 
					
				ans=ans-t[a[l]]*t[a[l]]+(t[a[l]]-1)*(t[a[l]]-1);
				--t[a[l]]; 
//			ans-=(t[a[l]]==0);
			++l;
		}
		while(l>st) { 
				ans=ans-t[a[l]]*t[a[l]]+(t[a[l]]+1)*(t[a[l]]+1);
				++t[a[l]];  
//			ans+=(t[a[l]]==1);
			--l;
		}
		while(r<ed) {
//			++t[a[r]]; 
				ans=ans-t[a[r]]*t[a[r]]+(t[a[r]]+1)*(t[a[r]]+1);
				++t[a[r]]; 
//			ans+=(t[a[r]]==1); 
			++r;
		}
		while(r>ed) { 
				ans=ans-t[a[r]]*t[a[r]]+(t[a[r]]-1)*(t[a[r]]-1);
				--t[a[r]]; 
			--r; 
		}
		aw[q[i].idx]=ans;
	} 
	for(reg i=1;i<=m;++i) { 
		write(aw[i]);
	}
    return 0;
}