#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define sz(a) (ll)(a.size())
#define pb push_back
#define popb pop_back
#define all(a) a.begin(),a.end()
#define llinf 1000000000000000LL
#define fi first
#define sc second
#define pll pair<ll,ll>
#define here cerr<<"===================================\n"
#define endl '\n'
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 200005
ll n,m,ans,it;
ll a[maxn],c[maxn];
ll last[maxn][2];
ll nxt[maxn][2];
ll col[maxn];
set<ll> s[2];
ll reshi(set<ll> v,set<ll> w){
ll cur = 0;
if(sz(v)<sz(w)) swap(v,w);
if(sz(w)==0&&sz(v)==0) return 0;
if(sz(w)==0){
bool col = 1;
ll x = *v.begin();
if(s[0].find(x)!=s[0].end()) col = 0;
col^=1;
for(ll x : v){
auto it = s[col].lower_bound(x);
ll y = llinf;
if(it!=s[col].end()){
if(abs(x-y)>abs(x-*it)) y = *it;
}
if(it!=s[col].begin()){
it--;
if(abs(x-y)>abs(x-*it)) y = *it;
}
cur+=abs(x-y);
}
return cur;
}
cur = llinf;
ll n = sz(v);
set<ll> lv,rv;
for(ll x : v){
if(sz(lv)<n/2) lv.insert(x);
else rv.insert(x);
}
ll x = *rv.begin(); rv.erase(rv.begin());
set<ll> lw,rw;
for(ll x : w) rw.insert(x);
vector<pll> vel;
while(sz(rw)){
ll y = *rw.begin();
rw.erase(rw.begin());
cur = min(cur,abs(x-y)+reshi(lv,lw)+reshi(rv,rw));
vel.pb({sz(lw),sz(rw)});
lw.insert(y);
}
return cur;
}
long long min_total_length(vector<int> r, vector<int> b) {
for(ll x : r) a[++n] = x;
for(ll x : b) c[++m] = x;
if(a[n]<c[1]){
reverse(all(r));
while(sz(r)>1&&sz(b)>1){
ans+=abs(r.back()-b.back());
r.popb(); b.popb();
}
if(sz(r)<sz(b)) swap(r,b);
for(ll x : r) ans+=abs(x-b[0]);
return ans;
}
if(n<=200&&m<=200){
for(ll x : r) s[1].insert(x);
for(ll x : b) s[0].insert(x);
return reshi(s[1],s[0]);
}
if(sz(r)>sz(b)) swap(r,b);
n = m = 0;
for(ll x : r) a[++n] = x;
for(ll x : b) c[++m] = x;
ll i = 0,j = 0;
while(i<n&&j<m){
if(r[i]<b[j]) col[++it] = 1,i++;
else col[++it] = 0,j++;
}
while(i<n) col[++it] = 1,i++;
while(j<m) col[++it] = 0,j++;
vector<ll> v(2,llinf);
for(ll i = 1;i<=n+m;i++){
last[i][0] = v[0]; last[i][1] = v[1];
v[col[i]] = i;
}
v[0] = v[1] = llinf;
for(ll i = n+m;i>=1;i--){
nxt[i][0] = v[0]; nxt[i][1] = v[1];
v[col[i]] = i;
}
set<ll> s;
for(ll x : b) s.insert(x);
for(ll i = 1;i<=n;i++){
ll x = a[i];
auto it = s.lower_bound(x);
ll y = llinf;
if(it!=s.end()){
if(abs(x-y)>abs(x-*it)) y = *it;
}
if(it!=s.begin()){
it--;
if(abs(x-y)>abs(x-*it)) y = *it;
}
if(y!=*it) it++;
s.erase(it);
ans+=abs(x-y);
}
for(ll i = 1;i<=m;i++){
ll x = c[i];
if(s.find(x)==s.end()) continue;
ll lf = last[x][1],rf = nxt[x][1];
ans+=min(abs(x-lf),abs(rf-x));
}
return ans;
}
/*
4 5
1 2 3 7
0 4 5 9 10
*/
