#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 3e5 + 5, B = 550;
int n, q;
int a[N], cnt[N], fre[N];
long long res[N];
vector<int> hev;
void add(int x, int y) {
--fre[cnt[x]];
++fre[cnt[x] += y];
}
long long S1(int i) {
return (long long) i * (i + 1) / 2;
}
long long S2(int i) {
return (long long) i * (i + 1) * (2 * i + 1) / 6;
}
long long calc(int i, int a, int b, int n) {
return (long long) a * i * (n - i) + S1(a - 1) * b * (n - 2 * i) - S2(a - 1) * b * b;
}
long long qry(int l) {
long long res = S1(l);
vector<array<int, 2>> cnd;
for (int i = 1; i < B; ++i) {
if (fre[i]) {
cnd.push_back({i, fre[i]});
}
}
for (int i : hev) {
if (cnt[i] >= B) {
cnd.push_back({cnt[i], 1});
}
}
sort(cnd.begin(), cnd.end());
int x = 0, y = l, m = 0;
for (auto [a, b] : cnd) {
int lt, rt;
if (m & 1) {
lt = (b + 1) / 2;
rt = b / 2;
} else {
lt = b / 2;
rt = (b + 1) / 2;
}
if (lt) {
res += calc(x, lt, a, l);
x += lt * a;
}
if (rt) {
y -= rt * a;
res += calc(y, rt, a, l);
}
m += b;
}
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
add(a[i], 1);
}
for (int i = 1; i < N; ++i) {
if (cnt[i] >= B) {
hev.push_back(i);
}
}
vector<array<int, 3>> que;
for (int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
que.push_back({l, r, i});
}
sort(que.begin(), que.end(), [&](const auto &a, const auto &b) {
return a[0] / B == b[0] / B ? a[1] < b[1] : a[0] < b[0];
});
int L = 1, R = n;
for (auto [l, r, id] : que) {
while (R < r) {
add(a[++R], 1);
}
while (L > l) {
add(a[--L], 1);
}
while (R > r) {
add(a[R--], -1);
}
while (L < l) {
add(a[L++], -1);
}
res[id] = qry(r - l + 1);
}
for (int i = 1; i <= q; ++i) {
cout << res[i] << "\n";
}
return 0;
}
