#include <bits/stdc++.h>
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(228);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umn(T& a, T b) {
return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
return a < b ? a = b, 1 : 0;
}
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int B = 560;
int calc(ve<int> a) {
int ans = 0;
fr (i, 0, sz(a) - 1) {
set<int> s;
fr (j, i, sz(a) - 1) {
s.insert(a[j]);
ans += sz(s);
}
}
return ans;
}
ll calc2(ve<int> a) {
int total = 0;
fe (x, a) total += x;
ll ans = 0;
int toLeft = 0;
ans += 1LL * sz(a) * total * (total + 1) / 2;
fr (i, 0, sz(a) - 1) {
int toRight = total - toLeft - a[i];
ans -= 1LL * toLeft * (toLeft + 1) / 2;
ans -= 1LL * toRight * (toRight + 1) / 2;
toLeft += a[i];
}
return ans;
}
ll calc3(ve<pii> a) {
assert(sz(a) <= B);
int total = 0;
int gr = 0;
fe (x, a) {
total += x.fi * x.se;
gr += x.se;
}
ll ans = 0;
ans += 1LL * gr * total * (total + 1) / 2;
int toLeft = 0;
fe (cur, a) {
fr (j, 1, cur.se) {
ans -= 1LL * toLeft * (toLeft + 1) / 2;
toLeft += cur.fi;
}
}
reverse(all(a));
toLeft = 0;
fe (cur, a) {
fr (j, 1, cur.se) {
ans -= 1LL * toLeft * (toLeft + 1) / 2;
toLeft += cur.fi;
}
}
return ans;
}
const int N = 3e5 + 5;
int n, q;
int a[N];
int cnt[N];
int rnd(int l, int r) {
return rng() % (r - l + 1) + l;
}
ll solve(ve<int> a) {
fe (x, a) cnt[x] = 0;
fe (x, a) cnt[x]++;
ve<pii> order;
fe (x, a) {
if (cnt[x]) {
order.pb({cnt[x], x});
cnt[x] = 0;
}
}
sort(all(order));
reverse(all(order));
{
ve<pii> st;
fe (cur, order) {
if (!sz(st) || cur.fi != st.back().fi) {
st.pb({cur.fi, 1});
} else {
st.back().se++;
}
}
deque<pii> d;
bool who = 0;
fe (x, st) {
if (x.se > 1) {
d.push_front({x.fi, x.se / 2});
d.pb({x.fi, x.se / 2});
x.se %= 2;
}
if (x.se) {
if (who == 0) {
if (sz(d) && d.front().fi == x.fi) d.front().se++;
else d.push_front({x.fi, 1});
} else {
if (sz(d) && d.back().fi == x.fi) d.back().se++;
else d.pb({x.fi, 1});
}
who ^= 1;
}
}
ve<pii> v;
fe (x, d) v.pb(x);
return calc3(v);
}
assert(0);
//
// deque<int> d;
// bool who = 0;
// fe (cur, order) {
// if (who == 0) d.push_front(cur.fi);
// else d.pb(cur.fi);
// who ^= 1;
// }
// ve<int> v;
// int now = 1;
// fe (x, d) {
// v.pb(x);
// }
// return calc2(v);
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> n >> q;
ve<int> v;
fr (i, 1, n) {
cin >> a[i];
v.pb(a[i]);
}
sort(all(v));
cout << solve(v) << "\n";
// int mn = 1e9;
// do {
// umn(mn, calc(v));
// } while (next_permutation(all(v)));
//
// cout << solve(v) << " " << mn << "\n";
//
// do {
// if (calc(v) == mn) {
// cout << "v: ";
// fe (x, v) cout << x << " ";
// cout << "\n";
// }
// } while (next_permutation(all(v)));
return 0;
}
