#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>


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

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> buc(k + 1);

    vector<array<int, 3>> q(m);
    for (int i = 0, x, y; i < m; i++) {
        cin >> x >> y;
        q[i] = {x, y, i};
    }
    vector<ll> ans(m);

    int B = sqrt(n);
    sort(q.begin(), q.end(), [&] (array<int, 3> x, array<int, 3> y) {
        int xid = x[0] / B, yid = y[0] / B;
        return xid == yid ? ((xid & 1) ? x[1] > y[1] : x[1] < y[1]) : xid < yid;
    });


    ll res = 0;
    function<void(int)> add = [&] (int i) {
        res -= buc[a[i]] * 1ll * buc[a[i]];
        buc[a[i]]++;
        res += buc[a[i]] * 1ll * buc[a[i]];
    };
    function<void(int)> sub = [&] (int i) {
        res -= buc[a[i]] * 1ll * buc[a[i]];
        buc[a[i]]--;
        res += buc[a[i]] * 1ll * buc[a[i]];
    };

    int L = 1, R = 0;
    for (auto X : q) {
        int l = X[0], r = X[1], id = X[2];
        while (R < r) add(++R);
        while (L > l) add(--L);
        while (R > r) sub(R--);
        while (L < l) sub(L++);
        assert(L == l && R == r);
        ans[id] = res;
    }

    for (int i = 0; i < m; i++) cout << ans[i] << '\n';
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
/*
g++ -std=c++14 1.cpp -o 1 && 1 < in.txt > out.txt
g++ -std=c++17 1.cpp -o 1 && ./1 < in.txt > out.txt

*/