#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010, SZ = 500;
int n, q, a[maxn], bel[maxn], occ[maxn], cnt[maxn];
long long ans[maxn];
vector<array<int, 3>> Q;
unordered_set<int> S;
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]), bel[i] = (i - 1) / SZ + 1;
}
for (int i = 1, l, r; i <= q; i++) {
scanf("%d %d", &l, &r);
Q.push_back({l, r, i});
}
sort(Q.begin(), Q.end(), [&](array<int, 3> p, array<int, 3> q) {
if (bel[p[0]] ^ bel[q[0]]) return bel[p[0]] < bel[q[0]];
return bel[p[0]] & 1 ? p[1] < q[1] : p[1] > q[1];
});
cnt[0] = maxn, S.insert(0);
auto ins = [&](int x, int coef) {
if (!--cnt[occ[x]]) S.erase(occ[x]);
occ[x] += coef;
if (!cnt[occ[x]]++) S.insert(occ[x]);
};
int l = 1, r = 0;
for (auto &p : Q) {
while (l > p[0]) ins(a[--l], 1);
while (r < p[1]) ins(a[++r], 1);
while (l < p[0]) ins(a[l++], -1);
while (r > p[1]) ins(a[r--], -1);
vector<pair<int, int>> V;
long long s = 0;
int all = 0;
for (int x : S) if (x) {
V.emplace_back(x, cnt[x]), all += cnt[x];
s += 1LL * x * x * cnt[x], ans[p[2]] += 1LL * x * (x + 1) / 2 * cnt[x];
}
sort(V.begin(), V.end());
ans[p[2]] += (1LL * (r - l + 1) * (r - l + 1) - s) / 2;
int pl = 1, pr = all, ls = 0, rs = 0;
for (auto &q : V) {
while (q.second--) {
if (pl <= all - pr) {
ans[p[2]] += 1LL * pl * q.first * (2 * ls + q.first - (r - l + 1));
pl++, ls += q.first;
} else {
ans[p[2]] += 1LL * pr * q.first * (r - l + 1 - 2 * rs - q.first);
pr--, rs += q.first;
}
}
}
}
for (int i = 1; i <= q; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
