#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SegmentTree {
vector<ll> t;
vector<ll> tag;
int sz;
void init(vector<int> a) {
int n = a.size();
sz = 1 << __lg(n) + !!(n & (n - 1));
t.resize(sz << 1), tag.resize(sz << 1);
for (int i = 0; i < n; ++i) {
t[i + sz] = a[i];
}
for (int i = sz - 1; i > 0; --i) {
t[i] = t[i << 1] + t[i << 1 | 1];
}
}
void rangeAdd(int l, int r, int v, int x, int lx, int rx) {
if (l >= rx || lx >= r) {
return;
}
if (l <= lx && rx <= r) {
tag[x] += v;
t[x] += 1LL * v * (rx - lx);
return;
}
int mid = (lx + rx) / 2;
rangeAdd(l, r, v, x << 1, lx, mid), rangeAdd(l, r, v, x << 1 | 1, mid, rx);
t[x] = t[x << 1] + t[x << 1 | 1] + (rx - lx) * tag[x];
}
void rangeAdd(int l, int r, int v) {
rangeAdd(l, r, v, 1, 0, sz);
}
ll rangeSum(int l, int r, int x, int lx, int rx) {
if (l >= rx || lx >= r) {
return 0;
}
if (l <= lx && rx <= r) {
return t[x];
}
int mid = (lx + rx) / 2;
return rangeSum(l, r, x << 1, lx, mid) + rangeSum(l, r, x << 1 | 1, mid, rx) +
(min(rx, r) - max(lx, l)) * tag[x];
}
ll rangeSum(int l, int r) {
return rangeSum(l, r, 1, 0, sz);
}
} 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 = 500;
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> answers(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;
}
t[0][0].init(vector(n, 0));
t[0][1].init(vector(n, 0));
t[1][0].init(vector(n, 0));
t[1][1].init(vector(n, 0));
vector<int> pos(m), cnt(m), ord(m);
iota(pos.begin(), pos.end(), 0);
ord = pos;
int siz[2]{(m + 1) / 2, m / 2};
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);
// cout << t[side][1].rangeSum(s, s + 1) << endl;
ans += t[side ^ 1][1].rangeSum(0, siz[side ^ 1]);
t[side ^ 1][0].rangeAdd(0, siz[side ^ 1], 1);
}
// for (int j = 0; j < m; ++j) {
// cout << j << ": " << t[pos[j] & 1][0].rangeSum(pos[j] / 2, pos[j] / 2 + 1) << " "
// << t[pos[j] & 1][1].rangeSum(pos[j] / 2, pos[j] / 2 + 1) << endl;
// }
// cout << endl;
cnt[i] += 1;
head[cnt[i]] = p;
ans += eval(i);
};
for (int i = 0; i < n; ++i) {
increase(a[i]);
}
cout << ans << '\n';
return 0;
}
