#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
if (!(cin >> N >> Q)) return 0;
vector<int> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
while (Q--) {
int L, R;
cin >> L >> R;
--L; --R;
// frequency for values 1..1000
const int MAXV = 1000;
vector<int> freq(MAXV + 1, 0);
for (int i = L; i <= R; ++i) ++freq[A[i]];
// collect block sizes (non-zero frequencies)
vector<int> blocks;
for (int v = 1; v <= MAXV; ++v) if (freq[v] > 0) blocks.push_back(freq[v]);
if (blocks.empty()) {
cout << 0 << '\n';
continue;
}
sort(blocks.begin(), blocks.end(), greater<int>());
deque<int> dq;
bool putLeft = true;
for (int s : blocks) {
if (putLeft) dq.push_front(s);
else dq.push_back(s);
putLeft = !putLeft;
}
int m = 0;
for (int s : blocks) m += s;
ll T = 1LL * m * (m + 1) / 2;
ll ans = 0;
int P = 0;
for (int s : dq) {
ll left_len = P;
ll right_len = m - (P + s);
ll left_sub = left_len * (left_len + 1) / 2;
ll right_sub = right_len * (right_len + 1) / 2;
ll intersect = T - left_sub - right_sub; // number of subarrays that include this value
ans += intersect;
P += s;
}
cout << ans << '\n';
}
return 0;
}
