#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 300'001;
const int BLOCK = 650;
struct Query {
int l, r, idx;
bool operator<(Query x) const {
if (l / BLOCK == x.l / BLOCK) return (l / BLOCK) & 1 ? r > x.r : r < x.r;
return l < x.l;
}
};
int a[MAXN], b[MAXN], c[BLOCK];
map<int, int> act;
ll ans[MAXN], negyzet[MAXN];
void inc(int v) {
if (b[v] < BLOCK) {
c[b[v]]++;
} else {
act[b[v]]++;
}
}
void dec(int v) {
if (b[v] < BLOCK) {
c[b[v]]--;
} else {
act[b[v]]--;
}
}
void add(int i) {
int v = a[i];
dec(v);
b[v]++;
inc(v);
}
void remove(int i) {
int v = a[i];
dec(v);
b[v]--;
inc(v);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
for (ll i = 1; i <= n; i++) {
negyzet[i] = negyzet[i-1] + i*i;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<Query> qrys(q);
for (int i = 0; i < q; i++) {
cin >> qrys[i].l >> qrys[i].r;
qrys[i].idx = i+1;
}
sort(qrys.begin(), qrys.end());
int l = 1, r = 0;
for (auto [nl, nr, idx] : qrys) {
while (r < nr) add(++r);
while (r > nr) remove(r--);
while (l < nl) remove(l++);
while (l > nl) add(--l);
deque<pair<ll, ll>> dq;
int d = 0;
auto push = [&](int a, int b) {
if (d) dq.emplace_back(a, b);
else dq.emplace_front(a, b);
d ^= 1;
};
for (auto it = act.rbegin(); it != act.rend(); it++) {
auto [len, cnt] = *it;
if (cnt == 0) continue;
if (cnt & 1) {
push(len, 1);
cnt--;
}
push(len, cnt/2);
push(len, cnt/2);
}
for (int i = BLOCK-1; i >= 1; i--) {
int len = i, cnt = c[i];
if (cnt == 0) continue;
if (cnt & 1) {
push(len, 1);
cnt--;
}
push(len, cnt/2);
push(len, cnt/2);
}
for (auto it = act.begin(); it != act.end();) {
auto [len, cnt] = *it;
if (cnt == 0) {
it = act.erase(it);
} else {
it++;
}
}
auto sum_arit = [&](ll start, ll d, ll cnt) {
return start*cnt + d * (cnt - 1) * cnt / 2;
};
ll pref = 0;
int x = nr-nl+1;
for (auto [len, cnt] : dq) {
ans[idx] += cnt * (len*(len+1)/2);
ans[idx] += cnt * (len*(x-len));
ans[idx] += (x - len) * sum_arit(pref, len, cnt);
ans[idx] -= pref * pref * cnt;
ans[idx] -= pref * sum_arit(0, 2*len, cnt);
ans[idx] -= len * len * negyzet[cnt-1];
pref += len*cnt;
}
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << "\n";
}
return 0;
}
