#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
const int sq = 821;
struct Sgt {
ll l, r, v, t, e;
int tl, tr;
Sgt *lft, *rht;
Sgt (int l, int r): l(0), r(0), v(0), t(0), e(1), tl(l), tr(r) {
if (tl != tr-1) {
int tm = tl+tr>>1;
lft = new Sgt(tl, tm);
rht = new Sgt(tm, tr);
}
}
void update (int i, int x) {
if (tl == tr-1) {
ll d = t+x;
l = r = t = d;
v = d*(d+1)/2;
return;
}
(i < lft->tr ? lft : rht)->update(i, x);
l = lft->l+rht->l+lft->e*rht->t;
r = lft->r+rht->r+lft->t*rht->e;
v = lft->v+rht->v+lft->t*rht->l+lft->r*rht->t;
t = lft->t+rht->t;
e = lft->e+rht->e;
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> vt(n);
for (int &i: vt) cin >> i;
vector<int> cc(vt.begin(), vt.end());
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (int &i: vt) i = lower_bound(cc.begin(), cc.end(), i)-cc.begin();
int m = cc.size()+cc.size()%2;
vector<int> cnt(m, 0);
vector<int> tag(m);
iota(tag.begin(), tag.end(), 0);
Sgt *sgt[2];
sgt[0] = new Sgt(0, m/2);
sgt[1] = new Sgt(0, m/2);
vector<map<int, int>> st(n+9);
for (int i = 0; i < m; i++) st[0][tag[i]] = i;
vector<pair<int, int>> qs(q);
for (auto &i: qs) {
cin >> i.f >> i.s;
i.f--;
}
vector<vector<int>> bucket(n/sq+1);
for (int i = 0; i < q; i++) bucket[qs[i].f/sq].push_back(i);
for (auto &i: bucket) sort(i.begin(), i.end(), [&](int a, int b) { return qs[a].s < qs[b].s;});
vector<int> ord;
vector<ll> ans(q);
for (auto i: bucket) for (int j: i) ord.push_back(j);
int l = 0, r = 0;
auto rmv = [&](int i) {
if (st[cnt[i]].size()) {
int h = (*st[cnt[i]].begin()).s;
if (h != i) {
st[cnt[i]].erase(tag[h]);
st[cnt[i]][tag[i]] = h;
swap(tag[h], tag[i]);
cnt[i]--;
st[cnt[i]][tag[i]] = i;
} else {
st[cnt[i]].erase(tag[i]);
cnt[i]--;
st[cnt[i]][tag[i]] = i;
}
} else {
st[cnt[i]].erase(tag[i]);
cnt[i]--;
st[cnt[i]][tag[i]] = i;
}
sgt[tag[i]%2]->update(tag[i]/2, -1);
};
auto add = [&](int i) {
if (st[cnt[i]].size()) {
int h = (*--st[cnt[i]].end()).s;
if (h != i) {
st[cnt[i]].erase(tag[h]);
st[cnt[i]][tag[i]] = h;
swap(tag[h], tag[i]);
cnt[i]++;
st[cnt[i]][tag[i]] = i;
} else {
st[cnt[i]].erase(tag[i]);
cnt[i]++;
st[cnt[i]][tag[i]] = i;
}
} else {
st[cnt[i]].erase(tag[i]);
cnt[i]++;
st[cnt[i]][tag[i]] = i;
}
sgt[tag[i]%2]->update(tag[i]/2, 1);
};
for (int i: ord) {
auto p = qs[i];
while (r < p.s) add(vt[r++]);
while (l > p.f) add(vt[--l]);
while (l < p.f) rmv(vt[l++]);
while (r > p.s) rmv(vt[--r]);
ans[i] = sgt[0]->v+sgt[1]->v+sgt[0]->t*sgt[1]->r+sgt[1]->t*sgt[0]->r;
}
for (ll i: ans) cout << i << "\n";
}
// no llama :(
// i miss you
