#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 4e5 + 5; ll a[maxn], pos[maxn], cnt[maxn]; struct node{ll l, r, k;}q[maxn]; ll ans[maxn], res; ll n, m, k; inline ll read(){ ll s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * w; } inline void print(ll x){ if(x < 0) x = ~x + 1, putchar('-'); if(x > 9) print(x / 10); putchar(x % 10 + '0'); } ll qpow(ll base, ll b){ ll ret = 1; while(b){ if(b & 1) ret *= base; base *= base; b >>= 1; } return ret; } void add(ll x){ cnt[a[x]]++; res -= qpow(cnt[a[x]] - 1, 2); res += qpow(cnt[a[x]], 2); } void sub(ll x){ cnt[a[x]]--; res -= qpow(cnt[a[x]] + 1, 2); res += qpow(cnt[a[x]], 2); } int main(){ n = read(), m = read(), k = read(); ll sz = sqrt(n); for(ll i = 1; i <= n; i++) a[i] = read(), pos[i] = i / sz; for(ll i = 0; i < m; i++) q[i].l = read(), q[i].r = read(), q[i].k = i; sort(q, q + m, [](node x, node y){return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];}); ll l = 1, r = 0; for(ll 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(ll i = 0; i < m; i++) print(ans[i]), putchar('\n'); return 0; }