RT

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

int n,m,k;
int l,r;
int a[50010];

int nl,nr,sum;
int c[1010];

void addl() {
	sum-=2*c[a[nl]]-1;
	c[a[nl]]--;
	nl++;
}

void addr() {
	nr++;
	c[a[nr]]++;
	sum+=2*c[a[nr]]-1;
}

void minl() {
	nl--;
	c[a[nl]]++;
	sum+=2*c[a[nl]]-1;
}

void minr() {
	sum-=2*c[a[nr]]-1;
	c[a[nr]]--;
	nr--;
}

struct query {
	int l,r,id,ans;
}q[50010];

int belong[50010];

bool cmp1(query a,query b) {
	if(belong[a.l]!=belong[b.l]) return belong[a.l]<belong[b.l];
	else return a.r<b.r;
}

bool cmp2(query a,query b) {
	return a.id<b.id;
}


int main() {
	scanf("%d%d%d",&n,&m,&k);
	int s=sqrt(n);
	for(int i=1;i<=s;i++) {
		for(int j=1;j<=s;j++) {
			belong[(i-1)*s+j]=i;
		}
	}
	for(int i=s*s;i<=n;i++) belong[i]=s+1;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) {
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	nl=1;
	nr=1;
	c[a[1]]=1;
	sum=1;
	sort(q+1,q+m+1,cmp1);
	for(int i=1;i<=m;i++) {
		while(nl<q[i].l) addl();
		while(nl>q[i].l) minl();
		while(nr>q[i].r) minr();
		while(nr<q[i].r) addr();
		q[i].ans=sum;
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++) {
		cout<<q[i].ans<<endl;
	}
}