#include <bits/stdc++.h>
using namespace std;
#define int long long
const int modulo = 1e9+7;
struct fenwick{
vector<int> treePrefix,treeMulti;
fenwick(int N):treeMulti(N+1),treePrefix(N+1){}
void add(int k,int x){
int m = x*k;
while(k<treeMulti.size()){
treeMulti[k]+=m;
treePrefix[k]+=x;
k+=k&-k;
}
}
pair<int,int> get(int k){
int mAns = 0;
int pAns = 0;
while(k){
mAns+=treeMulti[k];
pAns+=treePrefix[k];
k-=k&-k;
}
return {mAns,pAns};
}
pair<int,int> get(int L,int R){
auto rAns = get(R);
auto lAns = get(L-1);
int ans1 = rAns.first-lAns.first-(L-1)*(rAns.second-lAns.second);
int ans2 = (R-L+2)*(rAns.second-lAns.second)-ans1;
return {ans1,ans2};
}
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,Q;
cin >> N >> Q;
vector<int> arr(N);
for(int&i:arr)cin>>i;
vector<int> newarr;
{
int c=0;
map<int,int> comp;
for(int&i:arr){
if(!comp.count(i)){
comp[i]=c++;
newarr.emplace_back(0);
}
newarr[comp[i]]++;
}
}
sort(newarr.rbegin(),newarr.rend());
int cost = 0;
swap(arr,newarr);
int n = arr.size();
int t = 0;
fenwick ans(2*N);
int lPtr = N+1;
int rPtr = N;
for(int i=0;i<n;i++){
auto [prevCost,nextCost] = ans.get(lPtr,rPtr);
if(prevCost<nextCost){
ans.add(--lPtr,arr[i]);
} else {
ans.add(++rPtr,arr[i]);
swap(nextCost,prevCost);
}
cost+=prevCost*arr[i];
cost+=t*arr[i];
cost+=((arr[i]+1ll)*arr[i])/2ll;
t+=arr[i];
}
cout << cost << '\n';
}
