#pragma GCC target("avx2", "bmi")
#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 = 1580;
struct node {
ll l, r, v, t, e;
node(): l(0), r(0), v(0), t(0), e(1) {}
node (ll x): l(x), r(x), v(x*(x+1)/2), t(x), e(1) {}
node operator+ (node b) {
node c;
c.l = l+b.l+e*b.t;
c.r = r+b.r+b.e*t;
c.v = v+b.v+t*b.l+b.t*r;
c.t = t+b.t;
c.e = e+b.e;
return c;
}
};
struct Sgt {
int n;
vector<node> vt;
Sgt (int N): n(N), vt(2*N) {}
void update (int i, int x) {
i += n;
vt[i] = node(vt[i].t+x);
while (i >>= 1) vt[i] = vt[i<<1]+vt[i<<1|1];
}
};
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 = 1<<(int)log2(cc.size()*2);
vector<int> cnt(m, 0);
Sgt *sgt[2];
sgt[0] = new Sgt(m/2);
sgt[1] = new Sgt(m/2);
vector<pair<int, int>> st(n+9);
st[0] = {0, m};
for (int i = 1; i < n+9; i++) st[i] = {m, m};
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);
bool rev = false;
for (auto &i: bucket) {
sort(i.begin(), i.end(), [&](int a, int b) { return qs[a].s < qs[b].s;});
if (rev) reverse(i.begin(), i.end());
rev = !rev;
}
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) {
sgt[st[cnt[i]].f%2]->update(st[cnt[i]].f/2, -1);
st[cnt[i]].f++;
st[--cnt[i]].s++;
};
auto add = [&](int i) {
sgt[(st[cnt[i]].s-1)%2]->update((st[cnt[i]].s-1)/2, 1);
st[cnt[i]].s--;
st[++cnt[i]].f--;
};
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]->vt[1].v+sgt[1]->vt[1].v+sgt[0]->vt[1].t*sgt[1]->vt[1].r+sgt[1]->vt[1].t*sgt[0]->vt[1].r;
}
for (ll i: ans) cout << i << "\n";
}
// no llama :(
// i miss you
