#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define N 50010

using namespace std; int Ans[N],a[N],ans,blg[N],stack[N];

struct Node {int l,r,id;}q[N]; inline bool cmp(const Node &x,const Node &y) {return blg[x.l]==blg[y.l]?x.r<y.r:blg[x.l]<blg[y.l];}

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

inline void fix(int val,int delta)

{

	ans-=1ll*stack[val]*stack[val];

	stack[val]+=delta;

	ans+=1ll*stack[val]*stack[val];

}

int n,m,k;

void Test()

{

	puts("Fuck"); for(int i=1;i<=m;i++) printf("%d ",q[i].id); puts("");

}

int main()

{

	n=rd(),m=rd(),k=rd(); int unit=sqrt(n); int t=n/unit;

	for(int i=1;i<=t;i++)

	{

		for(int j=(i-1)*unit+1;j<=i*unit;j++) {a[j]=rd(); blg[j]=i;}

	}

	if(unit*t<n)

	{

		t++;

		for(int i=unit*(t-1)+1;i<=n;i++) a[i]=rd(),blg[i]=t;

	}

	for(int i=1;i<=m;i++) q[i].l=rd(),q[i].r=rd(),q[i].id=i;

	int l=1,r=0;

	sort(q+1,q+m+1,cmp); /* Test();  */for(int i=1;i<=m;i++)

	{

		while(l<q[i].l) fix(a[l],-1),l++;

		while(r>q[i].r) fix(a[r],-1),r--;

		while(l>q[i].l) l--,fix(a[l],1);

		while(r<q[i].r) r++,fix(a[r],1);

		Ans[q[i].id]=ans;

	}

	for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);

	return 0;

}