#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 4e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, q, a[N];
ii cnt[N];
int cntt[N];
void process(){
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
cnt[a[i]].fi++;
}
for(int i = 1; i <= 300000; i++){
cntt[cnt[i].fi]++;
cnt[i].se = i;
}
sort(cnt + 1, cnt + 300000 + 1, greater<ii>());
deque<int> dq;
vector<ii> vc1, vc2;
int total = 0;
for(int i = 1; i <= 300000; i++){
int temp1 = (cntt[i] + 1) / 2, temp2 = cntt[i] / 2;
if(!(total & 1)){
if(temp1) vc1.pb({i, temp1});
if(temp2) vc2.pb({i, temp2});
}
else{
if(temp2) vc1.pb({i, temp2});
if(temp1) vc2.pb({i, temp1});
}
total += cntt[i];
}
for(int i = vc2.size() - 1; i >= 0; i--) vc1.pb(vc2[i]);
int tol = 0, tol2 = 0, toll = 1;
/*
tol: total before, tol2: answer, toll: answer for i
*/
for(auto it : vc1){
// 1, 3, 6, 10
// 1, 2, 5, 6, 11, 12, ...
// 1, 2, 3, 7, 8, 9, 16, 17, 18, 28, 29, 30, ...
// 1, 1, 1, 7, 7, 7, 16, 16, 16, 28, 28, 28, ...
//
/*
it.se * (it.se + 1) / 2
tol + 1, tol + 2 * it.fi, tol + 5 * it.fi, ..., tol + 9 * it.fi
1 + 3 + 6 + 10 + 15 - 5
1*2/2 + 2*3/2 + 3*4/2 + 4*5/2 + 5*6/2 - 5
(1*2 + 2*3 + 3*4 + 4*5 + 5*6) / 2 - 5
((1*1 + 2*2 + 3*3 + 4*4 + 5*5) + (1+2+3+4+5)) / 2 - 5
*/
int temp = ((it.se * (it.se + 1) * (2 * it.se + 1)) / 6 + (it.se * (it.se + 1)) / 2) / 2 - it.se;
//cout << temp << "\n";
temp = temp * it.fi * it.fi + toll * it.fi * it.se;
//cout << temp << "\n";
temp += it.se * (it.fi * (it.fi - 1) / 2);
temp += tol * ((it.se * (it.se - 1)) / 2) * it.fi;
//cout << temp << "\n";
toll += ((it.se * (it.se + 1)) / 2) * it.fi + tol * (it.se - 1);
tol += it.fi * it.se;
//cout << toll << "\n";
toll += tol;
tol2 += temp;
//cout << it.fi << " " << it.se << "\n";
//cout << tol << " " << toll << " " << tol2 << "\n";
}
cout << tol2 << "\n";
// 0, 0, 4, 5, 10, 11
// 1, 2, 5, 6, 11, 12, 19, 20, 29, 30, 41
// 0, 0, 4, 4, 10, 10
/*
tol = toll = tol2 = 0;
for(int i = 299999; i >= 1; i -= 2){
tol2 += (cnt[i].fi * (cnt[i].fi + 1)) / 2;
tol2 += (cnt[i].fi * tol);
tol += cnt[i].fi;
toll += cnt[i].fi;
tol += toll;
}
for(int i = 2; i <= 300000; i += 2){
tol2 += (cnt[i].fi * (cnt[i].fi + 1)) / 2;
tol2 += (cnt[i].fi * tol);
tol += cnt[i].fi;
toll += cnt[i].fi;
tol += toll;
}*/
/*
for(int i = 1; i <= 300000; i++){
if(i & 1) for(int j = 1; j <= cnt[i].fi; j++) dq.push_front(cnt[i].se);
else for(int j = 1; j <= cnt[i].fi; j++) dq.push_back(cnt[i].se);
}
int cnt = 0, lst = -1;
tol = 0, tol2 = 0;
//cout << dq.size() << "\n";
while(dq.size()){
int u = dq.front();
//cout << u << "\n";
dq.pop_front();
cnt++;
if(lst != u) tol += cnt;
else tol++;
cout << tol << " ";
tol2 += tol;
lst = u;
}
cout << tol2 << "\n";*/
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
