#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 9,M = 5e4 + 9;
const int sqrtN = 259;
int read() {
	char c = getchar();
	int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}
int n,m,k;
struct block {
    int start,end,size;
} a[sqrtN];
struct query{
	int l,r,id;
} q[M];
int belong[N],len;
int seq[N],cnt[N];
int ans[N],c;
int lres,rres;
bool cmp(query x,query y){
	if(belong[x.l] == belong[y.l])
		return x.r < y.r;
	return belong[x.l] < belong[y.l];
}
void add(int x){
	c += 2 * cnt[x] + 1;
	cnt[x]++;
}
void del(int x){
	c -= 2 * cnt[x] - 1;
	cnt[x]--;
}
void build() {
    len = (int)sqrt(n);
    for (int i = 1; i <= len; i++) {
        a[i].start = n / len * (i - 1) + 1;
        a[i].end = n / len * i;
    }
    a[len].end = n;
    for (int i = 1; i <= len; i++) {
        for (int j = a[i].start; j <= a[i].end; j++)
            belong[j] = i;
        a[i].size = a[i].end - a[i].start + 1;
    }
}
signed main(){
    n = read();m = read();k = read();
    for(int i = 1;i <= n;i++)
		seq[i] = read();
	build();
	for(int i = 1;i <= m;i++){
		q[i].l = read();q[i].r = read();
		q[i].id = i;
	}
	sort(q + 1,q + m + 1,cmp);
    for(int i = 1;i <= m;i++){
		int L = q[i].l,R = q[i].r;
		while(lres > L)
			add(seq[--lres]);
		while(rres < R)
			add(seq[++rres]);
		while(lres < L)
			del(seq[lres++]);
		while(rres > R)
			del(seq[rres--]);
		ans[q[i].id] = c;
	}
	for(int i = 1;i <= m;i++){
		printf("%lld\n", ans[i]);//把这里改成ans[i] - 1就过了
	}
    return 0;
}