#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxN=50010;
struct ask{
    int l,r,id;
} s[maxN];
int q,num[maxN],ans[maxN],c[maxN];
bool cmp(ask a1,ask a2){
    if(a1.l/q!=a2.l/q) return a1.l/q<a2.l/q;
    else return a1.r<=a2.r;
}
signed main(){
    int n,m,k;
    cin>>n>>m>>k;
    q=sqrt(n);
    for(int i=1;i<=n;i++) cin>>num[i];
    for(int i=1;i<=m;i++){
        cin>>s[i].l>>s[i].r;
        s[i].id=i;
    }
    sort(s+1,s+m+1,cmp);
    int p=1,t=0,L=1,R=0;
    for(int i=0;i<=q;i++){
        while(s[p].l/q==i){
            while(L>s[p].l){
                L--;
                t+=2*c[num[L]]+1;
				c[num[L]]++;
            }
            while(L<s[p].l){
                c[num[L]]--;
                t-=2*c[num[L]]+1;
                L++;
            }
            while(R>s[p].r){
                c[num[R]]--;
                t-=2*c[num[R]]+1;
                R--;
            }
            while(R<s[p].r){
                R++;
                t+=2*c[num[R]]+1;
				c[num[R]]++;
            }
            ans[s[p].id]=t;
            if(p==m){
                for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
                return 0;
            }
            p++;
        }
    }
}