//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int bs = 1100;
struct query{
int l, r, id;
query(){l = r = id = 0;}
query(int a, int b, int c){l = a, r = b, id = c;}
};
int a[maxn], c[maxn], occ[maxn];
int lef[maxn], rig[maxn];
ll ans[maxn];
int distinct = 0;
void add(int col) {
int &p = c[col];
if (p == 0) distinct++;
if (occ[p] == 1) {
if (occ[p+1]) {
rig[lef[p]] = rig[p];
lef[rig[p]] = lef[p];
} else {
rig[lef[p]] = p+1;
lef[rig[p]] = p+1;
rig[p+1] = rig[p];
lef[p+1] = lef[p];
}
lef[p] = 0, rig[p] = maxn-1;
} else if (occ[p+1]==0) {
rig[p+1] = rig[p];
lef[p+1] = p;
lef[rig[p]] = p+1;
rig[p] = p+1;
}
occ[p]--, occ[p+1]++;
p++;
}
void del(int col) {
int &p = c[col];
if (p == 1) distinct--;
if (occ[p] == 1) {
if (occ[p-1]) {
rig[lef[p]] = rig[p];
lef[rig[p]] = lef[p];
} else {
rig[lef[p]] = p-1;
lef[rig[p]] = p-1;
rig[p-1] = rig[p];
lef[p-1] = lef[p];
}
lef[p] = 0, rig[p] = maxn-1;
} else if (occ[p-1]==0) {
rig[p-1] = p;
lef[p-1] = lef[p];
rig[lef[p]] = p-1;
lef[p] = p-1;
}
occ[p]--, occ[p-1]++;
p--;
}
int tot;
ll quad[maxn], cube[maxn];
ll getval(ll A, ll P, ll K) { //sum of A^2 + (A+P)^2 + ... + (A+(K-1)P)^2 + A + (A+P) + ... + (A + (K-1)P)
return K * (A * (A+1) + (tot - K*P-A)*(tot-K*P-A+1)) + quad[K] * (2*(tot-K*P+1)) * P + 2*cube[K] * P * P;
}
ll getans() {
int cur = rig[0];
ll ret = 0;
ll lc = 0, rc = 0;
while (cur <= tot) {
if (lc > rc) swap(lc, rc);
ll p = cur;
//debug(cur, occ[p]);
ll pl = (occ[p] + 1)/2, pr = occ[p] / 2;
ret += getval(lc, p, pl) + getval(rc, p, pr);
lc += pl * p, rc += pr * p;
cur = rig[cur];
}
return ret / 2;
}
int main() {
io
for (ll i = 1;i < maxn;i++) {
quad[i] = i * (i-1) / 2;
cube[i] = (i-1) * i * (2 * i - 1) / 6;
}
ll n, q;
cin >> n >> q;
for (int i = 0;i < n;i++) {
cin >> a[i];
}
for (int i = 0;i <= n;i++) rig[i] = maxn-1;
occ[0] = maxn-1;
vector<query> que;
for (int i = 0;i < q;i++) {
int l, r;
cin >> l >> r;
l--, r--;
que.push_back(query(l, r, i));
}
sort(que.begin(), que.end(), [&](query x, query y){
return x.l / bs == y.l / bs ? ((x.l / bs & 1) ? x.r < y.r : x.r > y.r) : (x.l < y.l);});
int cl = 0, cr = -1;
for (auto [l, r, id]:que) {
while (cr < r) add(a[++cr]);
while (cl > l) add(a[--cl]);
while (cr > r) del(a[cr--]);
while (cl < l) del(a[cl++]);
ans[id] = quad[r - l + 2] * distinct;
tot = r - l + 1;
ans[id] -= getans();
}
for (int i = 0;i < q;i++) cout << ans[i] << "\n";
}
