#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
6 1
2 4 3 5 4 3
1 6
**/
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 iq = 1; iq <= q; ++iq) {
int l, r; cin >> l >> r;
for (int j = l; j <= r; ++j) ++cnt[a[j]];
vector<int> f;
for (int j = 1; j < N; ++j) if (cnt[j] != 0) f.push_back(cnt[j]);
sort(f.begin(), f.end());
vector<int> v(f.size());
int id = 0;
for (int j = 0; j < f.size(); j += 2) v[id++] = f[j];
id = f.size() - 1;
for (int j = 1; j < f.size(); j += 2) v[id--] = f[j];
ll len = r - l + 1;
ll ans = len * (len + 1) / 2;
ll s = 0;
for (int j = v.size() - 1; j >= 0; --j) {
s += v[j];
if (j >= (v.size() + 1) / 2) ans += s * (len - s);
}
cout << ans << "\n";
}
}
