#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 5;
int a[MAXN], pos[MAXN], cnt[MAXN];
long long ans[MAXN];
long long res;


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

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void print(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

int n = read(), m = read(), k = read();

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

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

inline bool cmp(const Q &x, const Q &y) {
    return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
}

int main() {
    int siz = sqrt(n);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        pos[i] = i / siz;
    }
    for (int i = 0; i < m; i++) {
        q[i].l = read(), q[i].r = read();
        q[i].k = i;
    }
    sort(q, q + m, cmp);
    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++)
        print(ans[i]), putchar('\n');
    return 0;
}