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

#define int long long
const int maxn = 1e6+10;

int   a[maxn];
int pos[maxn];
int box[maxn];
int ans[maxn];

struct Q{
    int l,r,k;
}q[maxn];

int res = 0;
void add(int n){
    box[a[n]]++;
    res += box[a[n]]*box[a[n]]-(box[a[n]]-1)*(box[a[n]]-1);
}

void sub(int n){
    box[a[n]]--;
    res -= (box[a[n]]+1)*(box[a[n]]+1)-box[a[n]]*box[a[n]]; 
}

void run(){
    int n,m,k;
    cin>>n>>m>>k;

    //分块
    int siz = sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[i] = i/siz;
    }

    //读入询问
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].k = i;
    }

    sort(q+1,q+m+1,[](Q a,Q b){
        //如果左区间属于同一区块，那么按照右区间从小到大
        //否则，按照左区间的区块从小到大
        if(pos[a.l]==pos[b.l])
            return a.r<b.r;
        else
            return pos[a.l]<pos[b.l];
    });

    int l = 1;
    int r = 0;
    for(int i=1;i<=m;i++){
        if(q[i].l < l) add(--l);
        if(q[i].r > r) add(++r);
        if(q[i].l > l) sub(l++);
        if(q[i].r < r) sub(r--);
        ans[q[i].k] = res;
    }

    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --){
        run();
    }
    return 0;
}