#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
const int N = 3e5;
int n, q, a[N];
unordered_map<int, int> mp[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
while (q--) {
int l, r;
cin >> l >> r;
l--; r--;
auto it = mp[l].find(r);
if (it != mp[l].end()) {
cout << it->second << "\n";
continue;
}
int sz = r-l+1;
vector<int> vt(sz);
for (int i = l; i <= r; i++) {
vt[i-l] = a[i];
}
sort(all(vt));
//for (int& x : vt) cerr << x << " ";
//cerr << endl;
vector<int> s;
int cnt = 0;
for (int i = 0; i < sz; i++) {
if (i && vt[i] != vt[i-1]) {
s.push_back(cnt);
cnt = 1;
}
else cnt++;
}
s.push_back(cnt);
sort(all(s));
//for (int& x : s) cerr << x << " ";
//cerr << endl;
deque<int> dq;
int szS = s.size();
for (int i = 0; i < szS; i+=2) {
dq.push_back(s[i]);
}
for (int i = szS - (szS % 2 ? 2 : 1); i >= 0; i-=2) {
dq.push_back(s[i]);
}
//for (int& x : dq) cerr << x << " ";
//cerr << endl;
int ans = 0;
int L = 1;
while (!dq.empty()) {
int x = dq.front() - 1; dq.pop_front();
// sumar [L, L+x-1]
ans += (L+x-1)*(L+x)/2 - (L-1)*(L)/2;
L += x;
ans += L * (sz-L+1);
L++;
}
mp[l][r] = ans;
cout << ans << "\n";
}
}
