/**
* author: wxhtzdy
* created: 25.04.2023 21:06:35
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> l(q), r(q);
for (int i = 0; i < q; i++) {
cin >> l[i] >> r[i];
--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.01e5;
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;
for (int i = 0; i < c; i++) {
res += p * 1LL * (p - 1) / 2;
p += len;
res += (n - p + 1) * 1LL * (n - p + 2) / 2;
}
return res;
};
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) {
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';
}
return 0;
}
