#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int max_a = 300'000;
const int K = 540;
int32_t main() {
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
vector<vector<pair<int, pair<int, int>>>> gr((n + K - 1) / K);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
l--;
gr[l / K].push_back({r, {l, i}});
}
vector<int> ans(q);
for (int i = 0; i < gr.size(); i++) {
sort(gr[i].begin(), gr[i].end());
int l = i * K, r = i * K;
vector<int> fr(max_a);
vector<int> fr_fr(max_a);
fr_fr[0] = max_a;
set<pair<int, int>> s;
s.insert({0, max_a});
auto add_a = [&](int x) {
s.erase({fr[x], fr_fr[fr[x]]});
fr_fr[fr[x]]--;
if (fr_fr[fr[x]]) {
s.insert({fr[x], fr_fr[fr[x]]});
}
fr[x]++;
s.erase({fr[x], fr_fr[fr[x]]});
fr_fr[fr[x]]++;
s.insert({fr[x], fr_fr[fr[x]]});
};
auto del_a = [&](int x) {
s.erase({fr[x], fr_fr[fr[x]]});
fr_fr[fr[x]]--;
if (fr_fr[fr[x]]) {
s.insert({fr[x], fr_fr[fr[x]]});
}
fr[x]--;
s.erase({fr[x], fr_fr[fr[x]]});
fr_fr[fr[x]]++;
s.insert({fr[x], fr_fr[fr[x]]});
};
auto handle_blocks = [&](int L, int k, int l, int n, int& res) {
res += (k * (n * n + L) - k * l * l - k * (k - 1) * l * L - k * (k - 1) * (2 * k - 1) / 6 * L * L
- (n - l) * (n - l) * k + k * (k + 1) * (n - l) * L - k * (k + 1) * (2 * k + 1) / 6 * L * L) / 2;
};
for (auto seg: gr[i]) {
int q_l = seg.second.first, q_r = seg.first, q_i = seg.second.second;
while (r < q_r) {
add_a(a[r]);
r++;
}
while (l > q_l) {
l--;
add_a(a[l]);
}
while (l < q_l) {
del_a(a[l]);
l++;
}
int res = 0;
bool last = false; // false = left, true = right
int total_l = 0, total_r = 0;
//cerr << endl;
for (auto tmp: s) {
int L = tmp.first, total_k = tmp.second;
if (L == 0) {
continue;
}
int l_k = total_k / 2 + (total_k % 2 == 1 && last);
int r_k = total_k / 2 + (total_k % 2 == 1 && !last);
//cerr << l_k << ' ' << L << endl;
//cerr << r_k << ' ' << L << endl;
handle_blocks(L, l_k, total_l, r - l, res);
handle_blocks(L, r_k, total_r, r - l, res);
if (total_k % 2 == 1) {
last = !last;
}
total_l += l_k * L;
total_r += r_k * L;
}
ans[q_i] = res;
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}
