#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using ii = pair<int, int>;
template<class T>
struct bivec {
vector<T> neg, poz;
bivec(int sz, T v0) : neg(sz, v0), poz(sz, v0) {}
T &operator[](ll p) {
if(p >= 0) return poz[p];
return neg[-p - 1];
}
};
struct AIB {
ll n;
vll V;
AIB(ll N) : n(N), V(2 * N + 3, 0) {}
void update(ll p, ll v) {
p += n + 1;
while(p < V.size()) {
V[p] += v;
p += p & -p;
}
}
ll query(ll p) {
p += n + 1;
ll re = 0;
while(p) {
re += V[p];
p -= p & -p;
}
return re;
}
ll query(ll st, ll dr) {
return query(dr) - query(st - 1);
}
};
ll min_total_length(vi r, vi b) {
ll n = r.size(), m = b.size();
vector<ii> V;
for(auto it : r)
V.push_back({it, 1});
for(auto it : b)
V.push_back({it, -1});
sort(V.begin(), V.end());
const ll INF = 1e18;
ll len = n + m;
AIB delta(len);
ll orig = 0, slope0 = 0, ult = -1;
ll re = 0;
multiset<pair<int, ll> > D;
slope0 = -INF;
delta.update(orig, 2 * INF);
D.insert({orig, 2 * INF});
ll ref = 0;
for(auto [it, cul] : V) {
if(ult != -1) {
D.insert({orig, 2 * (it - ult)});
delta.update(orig, 2 * (it - ult));
slope0 -= it - ult;
}
if(cul == -1) {
re += (delta.query(orig) + slope0);
orig++;
} else {
orig--;
re -= (delta.query(orig) + slope0);
}
// ll v = re;
// for(ll i = orig - 1; i >= -len; --i) {
// v -= delta.query(-len, i) + slope0;
// }
// for(ll i = -len; i <= len; ++i) {
// if(i == orig) {
// cout << "(" << v << ") ";
// }
// else
// cout << v << " ";
// v += delta.query(-len, i) + slope0;
// }
// cout << "\n";
if(cul == 1) {
ll sl = slope0;
///voi sterge un sufix
while(!D.empty()) {
auto [p, v] = *D.rbegin();
sl = slope0 + delta.query(-len, p);
if(sl > 0) {
D.erase(D.find({p, v}));
delta.update(p, -v);
if(p < orig) {
re += (orig - p) * (-v);
}
if(sl - v < 0) {
D.insert({p, v - sl});
delta.update(p, v - sl);
if(p < orig) {
re += (orig - p) * (v - sl);
}
}
} else {
break;
}
}
// for(ll i = -len; i < len; ++i) {
// sl += delta.query(i, i);
// if(sl > 0) {
// delta.update(i, -sl);
// sl = 0;
// }
// }
} else {
///voi sterge un prefix
while(!D.empty()) {
auto [p, v] = *D.begin();
ll sl = slope0 + delta.query(-len, p - 1);
if(sl < 0) {
D.erase(D.find({p, v}));
slope0 += v;
delta.update(p, -v);
if(p > orig) {
re += (p - orig) * (- v);
}
if(v + sl > 0) {
slope0 -= v + sl;
delta.update(p, v + sl);
D.insert({p, v + sl});
if(p > orig) {
re += (p - orig) * (v + sl);
}
}
} else {
break;
}
}
// ll sl = slope0 + delta.query(-len, len);
// for(ll i = len; i > -len; --i) {
// sl -= delta.query(i, i);
// if(sl < 0) {
// delta.update(i, sl);
// if(i > orig) {
// re += (i - orig) * sl;
// }
// slope0 -= sl;
// sl = 0;
// }
// }
}
ult = it;
// ll v = re;
// for(ll i = orig - 1; i >= -len; --i) {
// v -= delta.query(-len, i) + slope0;
// }
// for(ll i = -len; i <= len; ++i) {
// if(i == orig) {
// cout << "(" << v << ") ";
// }
// else
// cout << v << " ";
// v += delta.query(-len, i) + slope0;
// }
// cout << "\n";
}
return re;
// ll orig = 0;
// bivec<ll> dp(n + m + 5, INF);
// dp[0] = 0;
// int ult = -1, len = n + m + 1;
// for(auto [it, cul] : V) {
// if(ult != -1) {
// for(int i = -len; i <= len; ++i) {
// dp[i] += abs(i - orig) * (it - ult);
// }
// orig -= cul;
// }
// ult = it;
// if(cul == 1) {
// for(int i = -len; i < len; ++i)
// dp[i + 1] = min(dp[i + 1], dp[i]);
// } else {
// for(int i = len; i > -len; --i)
// dp[i - 1] = min(dp[i - 1], dp[i]);
// }
//
// for(int i = -len; i <= len; ++i) {
// string s = to_string(dp[i]);
// if(dp[i] == INF) s = "INF";
// if(i == orig)
// cout << "(" << s << ") ";
// else
// cout << s << " ";
// }
// cout << "\n";
// }
// return dp[orig];
}
