#include<bits/stdc++.h>
using namespace std;
int n,m,a[50005],b[50005],block,k;
long long res=0,ans[50005];
struct query{
    int l,r,id;
}c[50005];
void add(int x){
    res+=2*b[a[x]]+1;
    b[a[x]]++;
}
void del(int x){
    res-=2*b[a[x]]-1;
    b[a[x]]--;
}
bool cmp(query x,query y){
    return (x.id/block!=y.id/block?x.id/block<y.id/block:((x.id/block)%2==0?x.r<y.r:x.r>y.r));
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    block=sqrt(n);
    for(int i=1;i<=m;i++){
        cin>>c[i].l>>c[i].r;
        c[i].id=i;
    }
    sort(c+1,c+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(l>c[i].l)add(--l);
        while(r<c[i].r)add(++r);
        while(l<c[i].l)del(l++);
        while(r>c[i].r)del(r--);
        ans[c[i].id]=res;
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

谁看看有没有哪写错了