#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 5e4+5;

int a[N], pos[N], cnt[N];
long long ans[N];
long long res;
struct Q{
    int l,r,k;
}q[N];

void Add(int n) { cnt[a[n]] ++ ; res += cnt[a[n]] * cnt[a[n]] - (cnt[a[n]] - 1) * (cnt[a[n]] - 1); }
void Sub(int n) { cnt[a[n]] -- ; res -= (cnt[a[n]] + 1) * (cnt[a[n]] + 1) - cnt[a[n]] * cnt[a[n]]; }

int main(){
#ifndef ONLINE_JUDGE
    freopen("D:\\in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    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 = 0;i < m;i ++ ){
        cin >> q[i].l >> q[i].r;
        q[i].k = i;
    }

    sort(q, q + m,[&](Q x,Q y){
        return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
    });

    int l = 1,r = 0;
    for(int i = 0;i < m;i ++ ){
        while(q[i].l < l) Add( -- l);
        while(q[i].r > r) Add( ++ r);
        while(q[i].l > l) Sub(l ++ );
        while(q[i].r < r) Sub(r -- );
        ans[q[i].k] = res;
    }

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

    // std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}