/*# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")*/
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll mod = 998244353;
const ll INF = 1LL << 60;
const int MAX = 1e9 + 10;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); i++)
#define repd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repd1(i, n) for (int i = (int)(n); i >= 1; i--)
#define repd2(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); i--)
template<class T> bool chmin(T &a, T b) {
if (a > b) {
a = b; return 1;
}
return 0;
}
template<class T> bool chmax(T &a, T b) {
if (a < b) {
a = b; return 1;
}
return 0;
}
struct edge {
int to, w;
};
ll inv(ll a) {
ll b = mod, u = 1, v = 0;
while(b) {
ll t = a / b;
a -= b * t;
swap(a, b);
u -= v * t;
swap(u, v);
}
u %= mod;
if (u < 0) u += mod;
return u;
}
template<class T> void print(vector<T> a) {
int n = a.size();
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
template<class T> int low_idx(const vector<T> &a, T x) {
return distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
template<class T> bool next_combination(T &bit, int N) {
T x = bit & -bit, y = bit + x;
bit = (((bit & ~y) / x) >> 1) | y;
return (bit < (1LL << N));
}
int next_combination(int sub) {
int x = sub & -sub, y = sub + x;
return (((sub & ~y) / x) >> 1) | y;
}
ll com2(int n) {
return (ll)n * (n - 1) / 2;
}
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> a(n), l(q), r(q);
rep(i, n) cin >> a[i];
rep(i, q) cin >> l[i] >> r[i];
vector<int> cnt(n, 0);
rep(i, n) cnt[a[i]-1]++;
sort(cnt.begin(), cnt.end());
ll res = 0;
ll sl = 0, sr = 0;
rep(i, n) {
if (i % 2 == 0) {
sl += cnt[i];
res += com2(sl-cnt[i]+1) + com2(n-sl+1);
}
else {
res += com2(sr+1) + com2(n-sr-cnt[i]+1);
sr += cnt[i];
}
//cerr << sl << " " << sr << " " << res << endl;
}
cout << (ll)n * (n + 1) / 2 * n - res << endl;
}
