#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SmartFenwick {
vector<ll> k, b;
int n{};
void init(int x) {
n = x;
k.resize(x + 1), b.resize(x + 1);
}
void addk(int i, ll v) {
for (int x = i + 1; x <= n; x += x & -x) {
k[x] += v;
}
}
void addb(int i, ll v) {
for (int x = i + 1; x <= n; x += x & -x) {
b[x] += v;
}
}
void rangeAdd(int l, int r, ll v) {
addk(l, v);
addk(r, -v);
addb(l, (l - 1) * -v);
addb(r, (r - 1) * v);
}
ll sum(int i) {
ll K = 0, B = 0;
for (int x = i + 1; x > 0; x -= x & -x) {
K += k[x], B += b[x];
}
return B + K * i;
}
ll rangeSum(int l, int r) {
return sum(r - 1) - sum(l - 1);
}
} t[2][2]; // (left/right), (L/R)
struct Query {
int l, r, block, idx;
bool operator<(Query oth) const {
if (oth.block != block) {
return block < oth.block;
}
return (block & 1) ? r > oth.r : r < oth.r;
}
};
constexpr int B = 200;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> yy = a;
sort(yy.begin(), yy.end());
yy.resize(unique(yy.begin(), yy.end()) - yy.begin());
for (int &x: a) {
x = lower_bound(yy.begin(), yy.end(), x) - yy.begin();
}
const int m = yy.size();
vector<Query> queries(q);
vector<ll> answer(q);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
l -= 1;
queries[i].l = l, queries[i].r = r, queries[i].block = l / B, queries[i].idx = i;
}
sort(queries.begin(), queries.end());
vector<int> head(n + 1);
for (int i = 1; i <= n; ++i) {
head[i] = m;
}
vector<int> pos(m), cnt(m), ord(m);
iota(pos.begin(), pos.end(), 0);
ord = pos;
int siz[2]{(m + 1) / 2, m / 2};
t[0][0].init(siz[0]);
t[0][1].init(siz[0]);
t[1][0].init(siz[1]);
t[1][1].init(siz[1]);
ll ans = 0;
int len = 0;
auto eval = [&](int i) {
return 1LL * cnt[i] * (len - cnt[i]) + 1LL * (cnt[i] + 1) * cnt[i] / 2;
};
auto increase = [&](int i) {
ans += len;
len += 1;
ans -= eval(i);
int p = pos[i];
int tail = head[cnt[i] + 1] - 1;
if (p != tail) {
int id = ord[tail];
pos[id] = p;
ord[p] = id;
pos[i] = tail;
ord[tail] = i;
p = tail;
}
int side = p % 2;
int s = p / 2;
if (side) {
ans += t[side][0].rangeSum(s + 1, siz[side]);
t[side][1].rangeAdd(s + 1, siz[side], 1);
t[side][0].rangeAdd(0, s, 1);
ans += t[side][1].rangeSum(0, s);
ans += t[side ^ 1][0].rangeSum(0, siz[side ^ 1]);
t[side ^ 1][1].rangeAdd(0, siz[side ^ 1], 1);
} else {
ans += t[side][1].rangeSum(s + 1, siz[side]);
t[side][0].rangeAdd(s + 1, siz[side], 1);
t[side][1].rangeAdd(0, s, 1);
ans += t[side][0].rangeSum(0, s);
ans += t[side ^ 1][1].rangeSum(0, siz[side ^ 1]);
t[side ^ 1][0].rangeAdd(0, siz[side ^ 1], 1);
}
cnt[i] += 1;
head[cnt[i]] = p;
ans += eval(i);
};
auto decrease = [&](int i) {
ans -= len;
len -= 1;
ans -= eval(i);
int p = pos[i];
int start = head[cnt[i]];
if (p != start) {
int id = ord[start];
pos[id] = p;
ord[p] = id;
pos[i] = start;
ord[start] = i;
p = start;
}
int side = p % 2;
int s = p / 2;
if (side) {
ans -= t[side][0].rangeSum(s + 1, siz[side]);
t[side][1].rangeAdd(s + 1, siz[side], -1);
t[side][0].rangeAdd(0, s, -1);
ans -= t[side][1].rangeSum(0, s);
ans -= t[side ^ 1][0].rangeSum(0, siz[side ^ 1]);
t[side ^ 1][1].rangeAdd(0, siz[side ^ 1], -1);
} else {
ans -= t[side][1].rangeSum(s + 1, siz[side]);
t[side][0].rangeAdd(s + 1, siz[side], -1);
t[side][1].rangeAdd(0, s, -1);
ans -= t[side][0].rangeSum(0, s);
ans -= t[side ^ 1][1].rangeSum(0, siz[side ^ 1]);
t[side ^ 1][0].rangeAdd(0, siz[side ^ 1], -1);
}
head[cnt[i]] = p + 1;
cnt[i] -= 1;
ans += eval(i);
};
int lx = 0, rx = 0;
for (auto [l, r, bl, i]: queries) {
while (rx < r) {
increase(a[rx++]);
}
while (lx > l) {
increase(a[--lx]);
}
while (lx < l) {
decrease(a[lx++]);
}
while (rx > r) {
decrease(a[--rx]);
}
answer[i] = ans;
}
for (int i = 0; i < q; ++i) {
cout << answer[i] << '\n';
}
return 0;
}
