#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
//#include<map>
#include<vector>
#include<math.h>
using namespace std;
#define int long long
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define INF 1e9
#define ll long long
#define MAXN 200005
const int _x[]={0,1,0,-1,0},_y[]={0,0,1,0,-1};
#define mem(a,n) memset(a,n,sizeof(a));
#define chkmax(a,b) a=a>b?a:b;
#define chkmin(a,b) a=a<b?a:b;
#include<set>
#include<stack>
#define DE puts("check");
int a[MAXN],sum[MAXN];
int block,ans;
int anss[MAXN];
int n,m,k;
struct Que{
	int l,r,num;
}q[MAXN];
bool cmp(Que q1,Que q2){
	return (q1.r/block)==(q2.r/block)?q1.l<q2.l:q1.r<q2.r;
}
void add(int i){
	++sum[a[i]];
	ans+=2*sum[a[i]]-1;
}
void del(int i){
	--sum[a[i]];
	ans-=2*sum[a[i]]+1;
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	block=sqrt(n);
	forr(i,1,n){
		scanf("%lld",&a[i]);
	}
	forr(i,1,m){
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].num=i;
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	forr(i,1,m){
		while(l<q[i].l){
			del(l++);
		}
		while(l>q[i].l){
			l--;
			add(l);
		}
		while(r<q[i].r){
			r++;
			add(r);
		}
		while(r>q[i].r){
			del(r++);
		}
		anss[q[i].num]=ans;
	}
	forr(i,1,m){
		printf("%lld\n",anss[i]);
	}
}