/**
* author: wxhtzdy
* created: 25.04.2023 21:06:35
**/
#include <bits/stdc++.h>
using namespace std;
int readint() {
int x = 0;
char c = getchar();
while (c < '0' || c > '9') {
c = getchar();
}
while ('0' <= c && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
return x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n = readint();
int q = readint();
//cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
//cin >> a[i];
a[i] = readint();
}
vector<int> l(q), r(q);
for (int i = 0; i < q; i++) {
//cin >> l[i] >> r[i];
l[i] = readint();
r[i] = readint();
--l[i]; --r[i];
}
const int BLOCK = 320;
vector<int> order(q);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (l[i] / BLOCK != l[j] / BLOCK) {
return l[i] < l[j];
} else {
return r[i] < r[j];
}
});
const int MAX = 3.0001e5;
vector<int> cnt(MAX);
vector<int> f(MAX);
vector<int> b;
vector<bool> was(MAX);
function<void(int)> Add = [&](int x) {
f[cnt[x]]--;
cnt[x]++;
f[cnt[x]]++;
if (f[cnt[x]] > 0) {
b.push_back(cnt[x]);
}
};
function<void(int)> Remove = [&](int x) {
f[cnt[x]]--;
cnt[x]--;
f[cnt[x]]++;
if (cnt[x] > 0) {
b.push_back(cnt[x]);
}
};
auto Solve = [&](int p, int len, int c, int n) {
long long res = 0;
// p ^ 2 - p + (p + len) ^ 2 - (p - len) + ... + (p + (c - 1) * len) ^ 2 - (p + (c - 1) * len)
// - p - (p - len) - (p + (c - 1) * len)
res += c * 1LL * p * p;
res += 2 * ((c - 1) * 1LL * c / 2) * len * p;
res += ((c - 1) * 1LL * c * (2 * (c - 1) + 1) / 6) * len * len;
res -= c * 1LL * p;
res -= ((c - 1) * 1LL * c / 2) * len;
n = n - p + 1;
c++;
// (n - c * len) ^ 2 + (n - c * len) + ... + (n - len) ^ 2 + (n - len) + n ^ 2 + n
res += c * 1LL * n * n;
res -= 2 * ((c - 1) * 1LL * c / 2) * len * n;
res += ((c - 1) * 1LL * c * (2 * (c - 1) + 1) / 6) * len * len;
res += n * 1LL * c;
res -= ((c - 1) * 1LL * c / 2) * len;
res -= (n * 1LL * n + n);
return res / 2;
};
int L = 0, R = -1;
vector<long long> ans(q);
for (int i : order) {
while (L < l[i]) {
Remove(a[L++]);
}
while (L > l[i]) {
Add(a[--L]);
}
while (R < r[i]) {
Add(a[++R]);
}
while (R > r[i]) {
Remove(a[R--]);
}
vector<int> new_b;
for (int x : b) {
if (x > 0 && !was[x] && f[x] > 0) {
new_b.push_back(x);
was[x] = true;
}
}
for (int x : b) {
if (x > 0 && f[x] > 0) {
was[x] = false;
}
}
swap(new_b, b);
sort(b.begin(), b.end());
int s = 0;
for (int x : b) {
s += f[x];
}
ans[i] = s * 1LL * (r[i] - l[i] + 1) * 1LL * (r[i] - l[i] + 2) / 2;
int curl = l[i], curr = r[i];
bool fl = false;
for (int j = 0; j < (int) b.size(); j++) {
int x = f[b[j]] / 2;
int y = f[b[j]] / 2;
if (f[b[j]] & 1) {
if (!fl) {
x += 1;
} else {
y += 1;
}
fl = !fl;
}
ans[i] -= Solve(curl - l[i] + 1, b[j], x, r[i] - l[i] + 1);
ans[i] -= Solve(r[i] - curr + 1, b[j], y, r[i] - l[i] + 1);
curl += x * b[j];
curr -= y * b[j];
}
}
for (int i = 0; i < q; i++) {
//cout << ans[i] << '\n';
printf("%lld\n", ans[i]);
}
return 0;
}
