#include <bits/stdc++.h>
#include "wiring.h"
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=2e5+100,inf=(ll)1e15;
ll dp[N];
ll par[N];
vector <pii> a;
ll solve(ll l,ll r,ll L,ll R){
ll zz=0;
if (l>0) zz=par[l-1];
ll ans=-(par[r]-zz)+par[R]-par[L-1];
ll z=r-l+1;
ll t=R-L+1;
if (z<t){
ans-=(t-z)*a[r].F;
}
else{
ans+=(z-t)*a[L].F;
}
return ans;
}
void devide(ll l,ll r,ll L,ll R,ll k){
if (r<l) return ;
ll mid=(r+l)/2;
ll id=L,mx=inf;
for (int i=L;i<=R;i++){
ll z=solve(mid,k,k+1,i)+min(dp[i],dp[i+1]);
if (z<=mx){
mx=z;
id=i;
}
}
dp[mid]=mx;
devide(mid+1,r,L,id,k);
devide(l,mid-1,id,R,k);
}
long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
for (auto u : r){
a.pb({u,0});
}
for (auto u : b){
a.pb({u,1});
}
sort(a.begin(),a.end());
par[0]=a[0].F;
for (int i=1;i<a.size();i++){
par[i]=par[i-1]+a[i].F;
}
memset(dp,63,sizeof dp);
dp[a.size()]=0;
vector <int> best;
for (int i=a.size()-2;i>-1;i--){
ll id=i;
if (i>0 && a[i-1].S==a[i].S) continue;
while(id<a.size() && a[id].S==a[i].S) id++;
if (id==a.size()) continue;
ll id2=id;
while(id2<a.size() && a[id2].S==a[id].S) id2++;
// cout << a[i].F << " " << i << " " << id << " " << id2 << endl;
/*
ll ww=i;
for (int j=id;j<id2;j++){
// cout << i << " " << id-1 << " " << j << " " << solve(i,id-1,id,j) << endl;
dp[i]=min(dp[i],solve(i,id-1,id,j)+min(dp[j],dp[j+1]));
if (dp[i]==solve(i,id-1,id,j)+min(dp[j],dp[j+1])){
ww=j;
}
}
best.pb(ww);
*/
// cout << i << " " << id-1 << " " << id+1 << " " << id2-1 << endl;
devide(i,id-1,id,id2-1,id-1);
// cout << i << " " << dp[i] << endl;
}
return dp[0];
}
/*
int32_t main() {
int32_t n, m;
assert(2 == scanf("%d %d", &n, &m));
vector<int32_t> r(n), b(m);
for(int i = 0; i < n; i++)
assert(1 == scanf("%d", &r[i]));
for(int i = 0; i < m; i++)
assert(1 == scanf("%d", &b[i]));
long long res = min_total_length(r, b);
printf("%lld\n", res);
return 0;
}
*/
/*
4 5
1 2 3 7
0 4 5 9 10
*/
