#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 2e5 + 5;
struct seg_tree{
ll mx[4*N], n;
void build(ll _n){
n = _n;
for(ll i = 0; i < 4*N; i++) mx[i] = 1e18;
}
void up(ll l, ll r, ll node, ll x, ll v){
if(r < x || l > x) return;
if(l == r){
mx[node] = min(v, mx[node]);
return;
}
ll m = (l + r)/2;
up(l, m, 2*node, x, v);
up(m+1,r,2*node + 1, x, v);
mx[node] = min(mx[2*node], mx[2*node + 1]);
return;
}
void up(ll x, ll v){
up(1,n,1,x,v);
}
ll get(ll l, ll r, ll node, ll x, ll y){
if(y < l || x > r) return 1e18;
if(x <= l && r <= y) return mx[node];
ll m = (l + r)/2;
return min(get(l, m, 2*node,x,y),get(m+1,r,2*node + 1,x,y));
}
ll get(ll x, ll y){
return get(1,n,1,x,y);
}
}A,B,C;
ll dp[N], L[N], R[N];
ll pref[N];
ll sum(ll l, ll r){
return pref[r] - pref[l - 1];
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector < ii > v;
v.pb({0, 0});
ll n = r.size();
ll m = b.size();
for(auto u : r){
v.pb({u, 0});
}
for(auto u : b){
v.pb({u, 1});
}
sort(v.begin(), v.end());
A.build(n + m);
B.build(n + m);
ll st[2] = {0, 0};
pref[0] = 0;
for(ll i = 1; i <= n + m; i++){
pref[i] = pref[i - 1] + v[i].ff;
st[v[i].ss] = i;
L[i] = st[v[i].ss^1] + 1;
}
st[0] = st[1] = n + m + 1;
for(ll i = n + m; i >= 1; i--){
st[v[i].ss] = i;
R[i] = st[v[i].ss^1] - 1;
}
dp[n + m + 1] = 0;
for(ll i = n + m; i >= 1; i--){
if(R[i] == n + m){
dp[i] = 1e18;
A.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff);
B.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff + (v[L[i]].ff - v[L[i] - 1].ff)*(i - L[i] + 1));
continue;
}
ll x = R[i];
ll l = L[x + 1];
ll r = R[x + 1];
ll gap = v[l].ff - v[x].ff;
ll mx = x - i + 1;
ll S = mx * v[x].ff - sum(i, x);
dp[i] = 1e18;
// A
dp[i] = min(dp[i], S + gap * mx + A.get(l, min(r, l + mx - 1)));
// B
if(l + mx <= r) dp[i] = min(dp[i], S + B.get(l + mx, r));
// mixed
if(l == r) dp[i] = min(dp[i], S + gap * mx + dp[l]);
//updates
// A
A.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff);
// B
B.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff + (v[L[i]].ff - v[L[i] - 1].ff)*(i - L[i] + 1));
}
return dp[1];
}
