#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int sz = 300000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, q;
cin >> n >> q;
vi a(n);
for (int &i: a) {
cin >> i;
--i;
}
vi l(q), r(q);
rep(i, q) {
cin >> l[i] >> r[i];
--l[i];
}
const int B = 1338;
vi ord(q);
iota(all(ord), 0);
sort(all(ord), [&](int i, int j) {
if (r[i] / B != r[j] / B) return r[i] / B < r[j] / B;
return l[i] < l[j];
});
vi cnt(sz);
vi mp(n + 1);
auto add = [&](int x) {
--mp[cnt[x]];
++mp[++cnt[x]];
};
auto del = [&](int x) {
--mp[cnt[x]];
++mp[--cnt[x]];
};
auto calc = [&](int s, int a, int k, int n) -> ll {
assert(a > 0 and k > 0 and s + a * k <= n / 2);
ll res = 0;
res -= (ll) k * (k + 1) * (2 * k + 1) / 6 * a * a;
res += (ll) k * (k + 1) / 2 * a * (n - 2 * s);
res += (ll) k * s * (n - s);
return res;
};
const int D = min(550, n + 1);
vi can;
{
vi v(sz);
rep(i, n) ++v[a[i]];
rep(i, sz) if (v[i] >= D) can.pb(i);
}
auto solve = [&mp, &calc, &D, &can, &cnt](int n) -> ll {
vp ls;
rep2(i, 1, D) if (mp[i]) ls.eb(i, mp[i]);
for (int i: can) if (cnt[i] >= D) ls.eb(cnt[i], 1);
sort(all(ls));
--ls.back().second;
vi v(2);
ll res = 0;
for (auto[f, s]: ls) {
if (!f or !s) continue;
// cerr << f << ' ' << s << endl;
if (v[0] > v[1]) swap(v[0], v[1]);
res += calc(v[0], f, (s + 1) / 2, n);
if (s >= 2) res += calc(v[1], f, s / 2, n);
v[0] += (s + 1) / 2 * f;
v[1] += s / 2 * f;
}
rep(i, 2) assert(v[i] <= n / 2);
res += (ll) n * (n + 1) / 2;
return res;
};
vl ans(q);
int nl = 0, nr = 0;
for (int i: ord) {
// cerr << i << endl;
while (nl > l[i]) add(a[--nl]);
while (nr < r[i]) add(a[nr++]);
while (nl < l[i]) del(a[nl++]);
while (nr > r[i]) del(a[--nr]);
ans[i] = solve(r[i] - l[i]);
}
rep(i, q) cout << ans[i] << '\n';
}
