#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 3e5 + 7;
const int K = 550;
int a[N], cnt[N];
/**
10 1
1 3 3 2 1 3 3 1 1 3
1 10
6 1
2 4 3 5 4 3
1 6
**/
int f[N], small[K], taken[K];
multiset<int> s;
void change(int x, int sgn) {
if (f[x] >= K) {
s.erase(s.find(f[x]));
} else {
--small[f[x]];
}
f[x] += sgn;
if (f[x] >= K) {
s.insert(f[x]);
} else {
++small[f[x]];
}
}
ll get(ll sum, ll x, ll total, ll cnt) {
// (pref + j) * (total - pref - j)
// (pref + 2 * j) * (total - pref - 2 * j)
// (pref + 3 * j) * (total - pref - 3 * j)
// pref * total - pref^2 - pref*j + j * total - j * pref - j^2
// pref * total + j * total - pref * (pref + j + j) - j^2
// total * (pref + j) - pref * (pref + 2*j) - j^2
// (pref + 2 * j) * (total - pref - 2 * j)
// pref * total - pref^2 - 2*pref*j + 2*j*total - 2*j*pref - 4*j^2
// total * (pref + 2*j) - pref * (pref + 4*j) - 4*j^2
// (pref + 3 * j) * (total - pref - 3 * j)
// total * (pref + 3*j) - pref * (pref + 6*j) - 9*j^2
ll ans = 0;
for (int j = sum; j <= sum + (cnt - 1) * x; j += x) {
ans += j * (total - j);
}
// cout << "! " << sum << " " << x << " " << total << " " << cnt << " => " << ans << "\n";
return ans;
}
ll get2(ll sum, ll x, ll total, ll cnt) {
ll ans = 0;
for (int j = sum + x; j <= sum + cnt * x; j += x) {
ans += j * (total - j);
}
return ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<array<int, 3>> qs;
vector<ll> sol(q + 1);
for (int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
sol[i] += (ll) (r - l + 1) * (r - l + 2) / 2;
qs.push_back({l, r, i});
}
sort(qs.begin(), qs.end(), [&](array<int, 3> a, array<int, 3> b) { return a[0] / K < b[0] / K || (a[0] / K == b[0] / K && a[1] < b[1]); });
int l = 1, r = 0;
for (int i = 0; i < q; ++i) {
int ql = qs[i][0];
int qr = qs[i][1];
int id = qs[i][2];
int total = qr - ql + 1;
while (l > ql) change(a[--l], +1);
while (r < qr) change(a[++r], +1);
while (l < ql) change(a[l++], -1);
while (r > qr) change(a[r--], -1);
vector<int> big;
for (auto x : s) big.push_back(x);
int start = 0;
{ // odd positions
ll pref = 0, cnt = 0;
for (int j = 1; j < K; ++j) {
taken[j] = 0;
if (cnt % 2 == 0) {
sol[id] += get(pref, j, total, (small[j] + 1) / 2);
taken[j] = (small[j] + 1) / 2;
cnt += (small[j] + 1) / 2;
pref += ((small[j] + 1) / 2) * 1LL * j;
} else {
sol[id] += get(pref, j, total, small[j] / 2);
taken[j] = small[j] / 2;
cnt += small[j] / 2;
pref += (small[j] / 2) * 1LL * j;
}
}
for (int j = cnt % 2; j < big.size(); j += 2) {
sol[id] += pref * (total - pref);
pref += big[j];
}
start = cnt % 2;
}
{ // even positions
ll pref = 0, cnt = 0;
for (int j = 1; j < K; ++j) {
sol[id] += get2(pref, j, total, small[j] - taken[j]);
cnt += small[j] - taken[j];
pref += (small[j] - taken[j]) * 1LL * j;
}
for (int j = 1 - start; j < big.size(); j += 2) {
sol[id] += pref * (total - pref);
pref += big[j];
}
}
}
for (int i = 1; i <= q; ++i) cout << sol[i] << "\n";
}
