#include <bits/stdc++.h>
// "o mare neintelegere"
// ok lil bro
using namespace std;
const int nmax = 3e5 + 1, qmax = 5e4 + 1, block = sqrt(nmax);
int f[nmax];
int ff[nmax];
unordered_set<int> fff;
void add_ff(int val) {
// cout << "added " << val << '\n';
fff.insert(val);
}
void remove_ff(int val) {
// cout << "removed " << val << '\n';
fff.erase(val);
}
void add_f(int val) {
if (f[val] > 0 && ff[f[val]] == 1) {
remove_ff(f[val]);
}
if (f[val] >= 0) {
ff[f[val]]--;
}
f[val]++;
// cout << "+ " << val << " (" << f[val] << ")\n";
if (f[val] >= 0) {
ff[f[val]]++;
}
if (f[val] > 0 && ff[f[val]] == 1) {
add_ff(f[val]);
}
}
void remove_f(int val) {
if (f[val] > 0 && ff[f[val]] == 1) {
remove_ff(f[val]);
}
if (f[val] >= 0) {
ff[f[val]]--;
}
f[val]--;
// cout << "- " << val << " (" << f[val] << ")\n";
if (f[val] >= 0) {
ff[f[val]]++;
}
if (f[val] > 0 && ff[f[val]] == 1) {
add_ff(f[val]);
}
}
int v[nmax];
int ans[qmax];
struct qry {
int l, r, i;
const bool operator < (qry ult) const {
if (l / block != ult.l / block) {
return l / block < ult.l / block;
}
return r < ult.r;
}
} Q[qmax];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
for (int i = 1; i <= q; i++) {
cin >> Q[i].l >> Q[i].r;
Q[i].i = i;
}
sort(Q + 1, Q + q + 1);
int dr = 0, st = 1;
for (int i = 1; i <= q; i++) {
while (st <= Q[i].l) {
remove_f(v[st]);
st++;
}
while (dr >= Q[i].r) {
remove_f(v[dr]);
dr--;
}
while (st > Q[i].l) {
st--;
add_f(v[st]);
}
while (dr < Q[i].r) {
dr++;
add_f(v[dr]);
}
// cout << "!" << Q[i].l << " " << Q[i].r << ": " << '\n';
vector<int> vals;
for (auto it : fff) {
vals.push_back(it);
}
sort(vals.begin(), vals.end());
int left = 1, right = Q[i].r - Q[i].l + 1;
int daria = Q[i].r - Q[i].l + 1;
int cur = 0, sumcnt = 0;
int cur_l = 0, cur_r = 0;
// cout << "\t\t" << st << " " << dr << ":\n";
for (auto it : vals) {
// cout << "!" << it << " " << ff[it] << '\n';
int cnt = ff[it];
sumcnt += cnt;
if (cnt % 2 == 1) {
if (st <= daria - dr + 1) {
cur_l = st;
cur_r = cur_l + it - 1;
cur += cur_l * (cur_l - 1) / 2;
cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
// cout << "1s " << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
st = cur_r + 1;
} else {
cur_r = dr;
cur_l = cur_r - it + 1;
cur += cur_l * (cur_l - 1) / 2;
cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
// cout << "2s " << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
dr = cur_l - 1;
}
cnt--;
}
while (cnt) {
cur_l = st;
cur_r = cur_l + it - 1;
cur += cur_l * (cur_l - 1) / 2;
cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
// cout << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
cur_r = dr;
cur_l = cur_r - it + 1;
cur += cur_l * (cur_l - 1) / 2;
cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
// cout << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
st += it, dr -= it;
cnt -= 2;
}
}
// cout << '\n';
// cout << sumcnt << ": " << daria << ", " << cur << '\n';
ans[Q[i].i] = sumcnt * daria * (daria + 1) / 2 - cur;
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << "\n";
}
return 0;
}
