#include <bits/stdc++.h>
using namespace std;
using l = long long;
void rotate(vector<int>, int);
#define pb push_back
#define sz(x) (int)(x).size()
struct B{
vector<l> t;
int n;
B(int n):n(n),t(n+5,0){}
void u(int i,l v){
i++;
while(i<=n){
t[i]+=v;
i+=i&-i;
}
}
l g(int i){
i++;
l r=0;
while(i>0){
r+=t[i];
i-=i&-i;
}
return r;
}
l g(int l,int r){
if(l>r) return 0;
return g(r)-g(l-1);
}
};
struct D{
vector<int> e;
D(int n):e(n+5,-1){}
int f(int x){ return e[x]<0?x:e[x]=f(e[x]); }
int s(int x){ return -e[f(x)]; }
void u(int x,int y){
x=f(x),y=f(y);
if(x==y) return;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y]; e[y]=x;
}
};
const int H=50000,Q=25000,I=1e9;
void energy(int n,vector<int> v){
B bs(H+5),bc(H+5);
vector<vector<int>> m(n);
vector<int> w(H+5,-1);
multiset<int> st;
set<pair<int,int>> cp;
map<int,int> mp;
D d(n+5);
for(int i=0;i<n;i++){
v[i]%=H;
int p=(v[i]+Q)%H;
if(mp.count(v[i])) d.u(mp[v[i]],i);
else if(mp.count(p)) d.u(mp[p],i);
else{
w[v[i]]=w[p]=i;
mp[v[i]]=mp[p]=i;
st.insert(p);
st.insert(v[i]);
}
}
for(int i=0;i<n;i++){
int r=d.f(i);
m[r].pb(i);
if(r==i) cp.insert({d.s(r),r});
bc.u(v[i],1);
bs.u(v[i],v[i]);
}
auto ac=[&](int x,int y){
return min(abs(x-y),H-abs(x-y));
};
auto ct=[&](int l){
l lres=0;
if(l<Q){
int p=l+Q;
lres+=bs.g(l,p-1)-bc.g(l,p-1)*l;
lres+=1ll*(H+l)*bc.g(p,H-1)-bs.g(p,H-1);
lres+=bc.g(0,l-1)*l-bs.g(0,l-1);
}else{
int p=(l+Q)%H;
lres+=bc.g(p+1,l)*l-bs.g(p+1,l);
lres+=bs.g(l+1,H-1)-bc.g(l+1,H-1)*l;
lres+=bc.g(0,p)*(H-l)+bs.g(0,p);
}
return lres;
};
auto chk=[&](vector<int>&v0,int a){
l r=0;
for(auto i:v0){
bc.u(v[i],-1);
bs.u(v[i],-v[i]);
}
for(auto i:v0){
r-=ct(v[i]);
r+=ct((v[i]+a)%H);
}
for(auto i:v0){
bc.u(v[i],1);
bs.u(v[i],v[i]);
}
return r;
};
auto go=[&](int x,int y,int a){
cp.erase({sz(m[y]),y});
st.erase(st.find(v[x]));
st.erase(st.find((v[x]+Q)%H));
for(auto i:m[x]){
bc.u(v[i],-1);
bs.u(v[i],-v[i]);
(v[i]+=a)%=H;
bc.u(v[i],1);
bs.u(v[i],v[i]);
}
while(!m[x].empty()){
m[y].pb(m[x].back());
m[x].pop_back();
}
cp.insert({sz(m[y]),y});
};
while(sz(cp)>1){
auto it=*cp.begin();
cp.erase(cp.begin());
int id=it.second;
int l=v[id];
int L=-1,R=-1,ml=I,mr=I;
auto p1=st.upper_bound(l);
if(p1!=st.end()){
ml=ac(*p1,l);
L=w[*p1];
}
if(l>=Q&&!st.empty()){
int x=*st.begin();
if(x!=l&&ac(x,l)<ml){
ml=ac(x,l);
L=w[x];
}
}
auto p2=st.lower_bound(l);
if(p2!=st.begin()){
p2--;
mr=ac(*p2,l);
R=w[*p2];
}
if(l<Q&& !st.empty()){
int x=*st.rbegin();
if(x!=l&&ac(x,l)<mr){
mr=ac(x,l);
R=w[x];
}
}
if(ml!=I&&chk(m[id],ml)>=0){
rotate(m[id],ml);
go(id,L,ml);
continue;
}
if(mr!=I&&chk(m[id],H-mr)>=0){
rotate(m[id],H-mr);
go(id,R,H-mr);
continue;
}
break;
}
vector<int> a,b;
for(int i=0;i<n;i++){
if(v[i]==v[0]) a.pb(i);
else b.pb(i);
}
if(sz(a)>sz(b)) swap(a,b);
while(sz(b)>n/2){
int x=b.back(); b.pop_back();
(v[x]+=Q)%=H;
rotate({x},Q);
}
}
