#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define N 50005

struct data{int x,y,t;}a[N];

int n,m,k,Len,b[N],c[N],ans[N],tot,L,R;

inline int bel(int x){return (x-)/Len+;}

inline bool cmp(data A,data B){

    return bel(A.x)==bel(B.x)?bel(A.y)<bel(B.y):bel(A.x)<bel(B.x);

}

inline void Del(int x){tot-=c[b[x]]*-,--c[b[x]];}

inline void Add(int x){tot+=c[b[x]]*+,++c[b[x]];}

int main(){

    scanf("%d%d%d",&n,&m,&k);Len=sqrt(n);

    register int i;

    for(i=;i<=n;++i) scanf("%d",&b[i]);

    for(i=;i<=m;++i) scanf("%d%d",&a[i].x,&a[i].y),a[i].t=i;

    sort(a+,a+m+,cmp);

    L=R=; c[b[]]=tot=;

    for(i=;i<=m;++i){

        while(L<a[i].x) Del(L++);

        while(L>a[i].x) Add(--L);

        while(R>a[i].y) Del(R--);

        while(R<a[i].y) Add(++R);

        ans[a[i].t]=tot;

    }

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

    return ;

}