#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;
int a[N], cnt[N];
ll get(vector<int> v) {
int n = v.size();
ll ans = 0;
for (int i = 0; i < n; ++i) {
set<int> s;
for (int j = i; j < n; ++j) {
s.insert(v[j]);
ans += s.size();
}
}
return ans;
}
/**
10 1
1 3 3 2 1 3 3 1 1 3
1 10
**/
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];
for (int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
for (int j = l; j <= r; ++j) ++cnt[a[j]];
vector<int> v;
deque<int> dq;
for (int j = 1; j < N; ++j) if (cnt[j] != 0) dq.push_back(cnt[j]);
sort(dq.begin(), dq.end());
while (dq.size() >= 2) {
v.push_back(dq.front());
v.push_back(dq.back());
dq.pop_back();
dq.pop_front();
}
if (dq.size() == 1) v.push_back(dq.back());
ll len = r - l + 1;
ll ans = len * (len + 1) / 2;
ll s = 0;
for (int j = 0; j < v.size(); ++j) {
ans += s * (len - s);
s += v[j];
}
cout << ans << "\n";
}
}
