样例没过，一直输出：

4
5
3
2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
vector<array<int,3>>v;
int mp[50005];
int block,id[50005];
int a[50005];
bool cmp(array<int,3> x,array<int,3> y){
	if (id[x[0]]!=id[y[0]]){
		return id[x[0]]<id[y[0]];
	}
	if (id[x[0]]&1){
		return x[1]>y[1];
	}
	return x[1]<y[1];
}
int ans[50005];
int cnt;
void add(int p){
	cnt-=mp[p]*mp[p];
	mp[p]++;
	cnt+=mp[p]*mp[p];
}
void del(int p){
	cnt-=mp[p]*mp[p];
	mp[p]--;
	cnt+=mp[p]*mp[p];
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	block=int(sqrt(n));
	for(int i=1;i<=n;i++){
		id[i]=(i-1)/block+1;
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		v.push_back({x,y,i});
	}
	sort(v.begin(),v.end(),cmp);
	int l=1,r=0;
	for(auto [x,y,z]:v){
		while(l<x){
			del(l++);
		}
		while(l>x){
			add(--l);
		}
		while(r<y){
			add(++r);
		}
		while(r>y){
			del(r--);
		}
		ans[z]=cnt;
	}
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}