#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;
} 
