#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_map>
#include <vector>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
typedef long long ll;
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
while (q--) {
int l, r;
cin >> l >> r;
--l;
--r;
unordered_map<int, int> freq;
freq.reserve(r - l + 1);
for (int i = l; i <= r; i++) freq[a[i]]++;
int m = r - l + 1;
int t = (int)freq.size();
vector<int> blocks;
for (auto &kv : freq) blocks.push_back(kv.second);
sort(blocks.begin(), blocks.end(), greater<int>());
ll L = 0, R = 0;
ll placed = 0;
deque<int> order;
for (int s : blocks) {
auto check = [&](bool right) -> pair<ll, deque<int>> {
deque<int> tmp = order;
if (right) tmp.push_back(s);
else tmp.push_front(s);
ll cur = 0;
int S = 0;
for (int x : tmp) S += x;
int prefix = 0;
for (int x : tmp) {
ll leftGap = prefix;
ll rightGap = S - x - prefix;
cur += leftGap * (leftGap + 1) / 2 + rightGap * (rightGap + 1) / 2;
prefix += x;
}
return {cur, tmp};
};
auto aRes = check(true);
auto bRes = check(false);
if (aRes.first >= bRes.first) {
order = std::move(aRes.second);
} else order = std::move(bRes.second);
}
ll totalSub = 1LL * m * (m + 1) / 2;
ll sumGaps = 0;
int S = 0;
for (int x : order) S += x;
int prefix = 0;
for (int x : order) {
ll leftGap = prefix;
ll rightGap = S - x - prefix;
sumGaps += leftGap * (leftGap + 1) / 2 + rightGap * (rightGap + 1) / 2;
prefix += x;
}
ll ans = (ll)freq.size() * totalSub - sumGaps;
cout << ans << "\n";
}
return 0;
}
