#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"
const int MAX_N = 3e5;
int n, Q;
int a[1 + MAX_N];
ll solve(vector <int> &v) {
int sz = v.size ();
ll ans = 0;
for (int l = 0; l < sz; l++) {
map <int, int> freq;
for (int r = l; r < sz; r++) {
freq[v[r]]++;
ans += freq.size();
}
}
return ans;
}
ll brute_force() {
vector <int> order(n);
for (int i = 0; i < n; i++)
order[i] = i + 1;
ll ans = (1ll << 60);
vector <int> best;
do {
vector <int> v;
for (int i : order)
v.push_back(a[i]);
ll cnt = solve(v);
if (ans > cnt) {
best = v;
ans = cnt;
}
} while (next_permutation(order.begin(), order.end()));
cout << ans << "\n";
for (int x : best)
cout << x << " ";
cout << "\n";
return ans;
}
/// maybe we need to add the one with lowest freq closer to the edges
/// can we do this greedy or just by dp? greedy works!
int freq[1 + MAX_N];
ll get_div(int l, int r, int sz) {
ll ans = 0;
/// out out
ans += 1ll * (l - 1) * (sz - r);
/// in out
ans += 1ll * (r - l + 1) * (sz - r);
/// out in
ans += 1ll * (r - l + 1) * (l - 1);
/// in in
ans += 1ll * (r - l + 1) * (r - l + 2) / 2;
// dbg (ans);
return ans;
}
ll greedy_v1() {
for (int i = 1; i <= n; i++)
freq[a[i]]++;
vector <int> values;
for (int i = 1; i <= MAX_N; i++)
if (freq[i])
values.push_back(freq[i]);
sort (values.begin(), values.end());
int l = 1, r = n;
int putL = 0, putR = 0;
ll ans = 0;
for (int cnt : values) {
if (putL < putR) {
putL += cnt;
ans += get_div(l, l + cnt - 1, n);
l += cnt;
}
else {
putR += cnt;
ans += get_div(r - cnt + 1, r, n);
r -= cnt;
}
}
return ans;
}
const int RADMAX = 500;
struct Query {
int st;
int dr;
int ind;
};
vector <Query> q[RADMAX];
ll sol[1 + MAX_N];
int car[1 + MAX_N];
bool cmp (Query a, Query b) {
return a.dr < b.dr;
}
int rad;
inline int bucket (int x) {
return x / rad;
}
multiset <int> st;
void upd(int value, int val) {
if (car[value])
st.erase(st.find(car[value]));
car[value] += val;
if (car[value])
st.insert(car[value]);
}
ll get(int L, int R){
int putL = 0, putR = 0;
ll ans = 0;
int l = 1, r = R - L + 1;
for (int cnt : st) {
if (putL < putR) {
putL += cnt;
ans += get_div(l, l + cnt - 1, R - L + 1);
l += cnt;
}
else {
putR += cnt;
ans += get_div(r - cnt + 1, r, R - L + 1);
r -= cnt;
}
}
return ans;
}
void query_mode() {
rad = sqrt(n);
for (int i = 1; i <= Q; i++) {
int x, y;
cin >> x >> y;
q[bucket (x)].push_back ({x, y, i});
}
for (int b = 0; b <= rad; b++) {
sort (q[b].begin (), q[b].end (), cmp);
memset (car, 0, sizeof (car));
st.clear();
int dr = (b + 1) * rad;
for (auto w : q[b]) {
while (dr <= w.dr) {
upd(a[dr], 1);
dr++;
}
int bound = min (w.dr, (b + 1) * rad - 1);
for (int i = w.st; i <= bound; i++)
upd(a[i], 1);
sol[w.ind] = get(w.st, w.dr);
for (int i = w.st; i <= bound; i++)
upd(a[i], -1);
}
}
for (int i = 1; i <= Q; i++)
cout << sol[i] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> Q;
for (int i = 1; i <= n; i++)
cin >> a[i];
query_mode();
/*
while (q--) {
int l, r;
cin >> l >> r;
}
ll ans_brute = brute_force();
ll ans_greddy = greedy_v1();
cout << ans_brute << " " << ans_greddy << "\n";*/
return 0;
}
/**
4 2
1 1 1 1
1 2
2 4
**/
