快读没问题，快写没问题

#include <bits/stdc++.h>
#define gl(s) ((((s)-1)*B)+1)
#define gr(s) ((s)*B)
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long ll;
const int maxn = 5e4+7;
ll ans[maxn],c;
int g[400],arr[maxn],col[maxn];
int n,B,tot,m,k;
template<typename T>void read(T& n)
{
    T f=1,k=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){f=-1;}c=getchar();}
    while(c<='9'&&c>='0'){k=(k<<3)+(k<<1)+c-'0';c=getchar();}
    n=f*k;
}
  
template<typename T>void write(T x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

struct node {
	int l,r,id;
}q[maxn];

bool cmp(node a,node b) {
	return (g[a.l]==g[b.l])?((g[a.l]&1)?(a.r>b.r):(a.r<b.r)):(g[a.l]<g[b.l]);
}

void add(int x) {
	c+=(col[arr[x]]<<1);
	++c;
	++col[arr[x]];
}

void del(int x) {
	c-=(col[arr[x]]<<1);
	++c;
	--col[arr[x]];
}

signed main() {
	read(n),read(m),read(k);
	B=ceil(double(sqrt(n*1.0)));
	tot=n/B;
	if(tot*B<n)++tot;
	for(int i=1;i<=n;++i) {
		g[i]=(i-1)/B+1;
		read(arr[i]);
	}
	for(int i=1;i<=m;++i) {
		read(q[i].l);
		read(q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i) {
		while(l>q[i].l) --l,add(l);
		while(r<q[i].r) ++r,add(r);
		while(l<q[i].l)del(l),++l;
		while(r>q[i].r)del(r),--r;
		ans[q[i].id]=c;
	}
	for(int i=1;i<=m;++i)
		write(ans[i]),enter;
    return 0;
}