#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;
const int SQRT = 547, MAX = 3e5;
int main() {
int n, q;
cin >> n >> q;
int a[n];
for (int &ai: a) cin >> ai;
vector<array<int, 3>> qu(q);
for (int i = q; i--;) {
cin >> qu[i][0] >> qu[i][1];
--qu[i][0], --qu[i][1];
qu[i][2] = i;
}
sort(all(qu), [&] (auto &a, auto &b) { return a[0] / SQRT == b[0] / SQRT ? a[1] < b[1] : a[0] < b[0]; });
int l = 0, r = -1, freq[MAX + 1]{n + 1}, ffreq[MAX + 1]{};
vector<int> nxt(MAX + 1, -1), pre(MAX + 1, -1);
auto p = [&] (int i, int j) {
if (~i) nxt[i] = j;
if (~j) pre[j] = i;
};
auto add = [&] (int i) {
if (not ffreq[++freq[i = a[i]]]++) {
p(freq[i], nxt[freq[i] - 1]);
p(freq[i] - 1, freq[i]);
}
if (not --ffreq[freq[i] - 1]) p(pre[freq[i] - 1], freq[i]);
};
auto rem = [&] (int i) {
if (not ffreq[--freq[i = a[i]]]++) {
p(pre[freq[i] + 1], freq[i]);
p(freq[i], freq[i] + 1);
}
if (not --ffreq[freq[i] + 1]) p(freq[i], nxt[freq[i] + 1]);
};
vector<ll> ans(q);
ll squares[MAX + 1]{};
for (int i = 1; i <= n; ++i) squares[i] = squares[i - 1] + (ll) i * (i + 1) / 2;
for (auto &[li, ri, i]: qu) {
while (r < ri) add(++r);
while (r > ri) rem(r--);
while (l > li) add(--l);
while (l < li) rem(l++);
vector<pint> raw, lhs, rhs;
bool b = false;
for (int f = 0; ~(f = nxt[f]);) raw.emplace_back(f, ffreq[f]);
for (int j = raw.size(); j--;) {
(b ? lhs : rhs).emplace_back(raw[j].first, (raw[j].second + 1) / 2);
(b ? rhs : lhs).emplace_back(raw[j].first, raw[j].second / 2);
b ^= raw[j].second & 1;
}
reverse(all(lhs));
lhs.insert(lhs.end(), all(rhs));
ll iw = 0;
int sum = 0;
for (auto &[f, cnt]: lhs) {
if (not cnt) continue;
ans[i] += (iw * cnt + sum * (ll) cnt * (cnt + 1) / 2) * f;
if (cnt > 1) ans[i] += (ll) (cnt + 2) * (cnt - 1) / 2 * f * f;
ans[i] += (ll) f * (f + 1) / 2 * cnt;
iw += (ll) sum * cnt + (ll) f * cnt * (cnt + 1) / 2;
sum += f * cnt;
}
}
for (int i = q; i--;) cout << ans[i] << endl;
}
