#include<bits/stdc++.h>
using namespace std;

const int N=5e4+5,M=1e6+5;

int n,q,k,cnt[M],pos[N],a[N],l[N],r[N],ql=1,qr=0,tot;//ans是答案，cnt是出现次数，a是每个数，l，r，tot是分块相关的操作 

long long ans;

inline int read(){
	int x=0,fh=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*fh;
}

struct node{
	int ls,rs;
}t[N];

bool cmp(node a,node b){
	return pos[a.ls]!=pos[b.ls]?a.ls<b.ls:a.rs<b.rs;
}

void del(int k){
	ans-=cnt[a[k]]+cnt[a[k]]-1;
	--cnt[a[k]];
}

void add(int k){
	++cnt[a[k]];
	ans+=cnt[a[k]]+cnt[a[k]]-1;
}

int main(){
	n=read();q=read();k=read();
	for(int i=1;i<=n;++i) a[i]=read();
	int p=sqrt(n);
	for(tot=1;tot<=p;++tot){
		l[tot]=1+p*(tot-1);
		r[tot]=p*tot;
		if(tot==p) r[tot]=n;//建立分块 
		for(int i=l[tot];i<=r[tot];++i) pos[i]=tot;
	}
	for(int i=1;i<=q;++i){
		t[i].ls=read();t[i].rs=read();
	}//输入 
	sort(t+1,t+1+q,cmp);
	for(int i=1;i<=q;++i){
		while(l[ql]!=l[t[i].ls]){//跳块 
		ql=t[i].ls;qr=ql-1;ans=0;
		memset(cnt,0,sizeof(cnt));
		}
		while(ql>t[i].ls) add(--ql);
		while(ql<t[i].ls) del(ql++);
		while(qr>t[i].rs) del(qr--);
		while(qr<t[i].rs) add(++qr);
		printf("%lld\n",ans);
	}
	
	return 0;
}