#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
for (int i = 0; i < q; ++i) {
int l, r; cin >> l >> r;
l--;
vector<int> v;
vector<int> app(300002);
v.reserve(r - l);
int s = r - l;
for (int j = l; j < r; ++j) {
v.push_back(arr[j]);
}
for (auto x : v) {
app[x]++;
}
vector<pii> v2;
for (auto x : v) {
v2.emplace_back(app[x],x);
}
std::sort(v2.begin(), v2.end());
vector<int> orderA, orderB;
int last = 0;
bool dir = true;
for (auto [a, x] : v2) {
if (last != x) dir = !dir;
if (dir) orderA.emplace_back(x);
else orderB.emplace_back(x);
last = x;
}
vector<int> order;
for (auto x : orderA) {
order.push_back(x);
}
std::reverse(orderB.begin(), orderB.end());
for (auto x : orderB) {
order.push_back(x);
}
int ans = 0;
for (int j = 0; j < s; ++j) {
set<int> num;
for (int k = j; k < s; ++k) {
num.insert(order[k]);
ans += num.size();
}
}
cout << ans << "\n";
}
return 0;
}
