#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+9;
long long f[maxn];
const long long inf=1e18;
/*
2 type of update
rrrrbrrrr (just 1 blue)
rrrrbbbb (red>=blue or blue>=red)
*/
long long l[maxn],r[maxn];
vector<long long>del1[maxn],del2[maxn],del3[maxn],add1[maxn],add2[maxn],add3[maxn];//
long long pf[maxn];
long long min_total_length(vector<int> red, vector<int> blue) {
int n=sz(red),m=sz(blue);
vector<pli>a;
a.pb({0,0});
for1(i,0,n-1)a.pb({red[i]+1,1});
for1(i,0,m-1)a.pb({blue[i]+1,0});
sort(all(a));
f[0]=0;
n=n+m;
for1(i,1,n)pf[i]=pf[i-1]+a[i].fi;
for1(i,1,n)f[i]=inf;
for2(i,n,1){
r[i]=i;
if (i<n&&a[i].se==a[i+1].se)r[i]=r[i+1];
}
for1(i,1,n){
l[i]=i;
if (i>1&&a[i].se==a[i-1].se)l[i]=l[i-1];
}
multiset<long long>f1,f2,f3;//f1 mean opposite larger, f2 opposite smaller and f3 just 1 opposite
for1(i,0,n){
for (auto v:add1[i]){
f1.insert(v);
//if (i==n)cerr<<v<<'\n';
}
for (auto v:add2[i])f2.insert(v);
for (auto v:add3[i])f3.insert(v);
if (i>0){
if (!f1.empty()){
auto it=f1.begin();
long long cost=-a[l[i]].fi*(i-l[i]+1)+pf[i]-pf[l[i]-1];
f[i]=min(f[i],(*it)+cost);
}
if (!f2.empty()){
auto it=f2.begin();
f[i]=min(f[i],(*it)+pf[i]-pf[l[i]-1]-a[l[i]-1].fi*(i-l[i]+1));
}
if (!f3.empty()){
auto it=f3.begin();
long long cost=1ll*pf[i]-pf[l[i]-1]-a[l[i]-1].fi*(i-l[i]+1);
f[i]=min(f[i],(*it)+cost);
}
}
for (auto v:del1[i])f1.erase(f1.find(v));
for (auto v:del2[i])f2.erase(f2.find(v));
for (auto v:del3[i])f3.erase(f3.find(v));
if (i==n)break;
//update for type 1
if (r[i+1]+1<=n){
long long l1=i+1,r1=r[i+1],l2=r[i+1]+1,r2=r[r[i+1]+1];
add1[l2].pb(f[i]-(pf[r1]-pf[l1-1])+a[l2].fi*(r1-l1+1));
//for (auto v:add1[n])cerr<<v<<'\n';
del1[min(l2+(r1-l1+1)-1,r2)].pb(f[i]-(pf[r1]-pf[l1-1])+a[l2].fi*(r1-l1+1));
}
//update for type 2
if (r[i+1]+1<=n){
long long l1=i+1,r1=r[i+1],l2=r[i+1]+1,r2=r[r[i+1]+1];
if (r2-l2+1>r1-l1+1){
l2+=(r1-l1+1);
add2[l2].pb(f[i]-(pf[r1]-pf[l1-1])+a[r1].fi*(r1-l1+1));
del2[r2].pb(f[i]-(pf[r1]-pf[l1-1])+a[r1].fi*(r1-l1+1));
}
}
//update for type 3
if (r[i+1]+2<=n&&a[r[i+1]+2].se==a[i+1].se){
long long l1=i+1,r1=r[i+1],l2=r[i+1]+1,r2=r[i+1]+1,l3=r[i+1]+2,r3=r[r[i+1]+2];
long long cost=a[l2].fi*(r1-l1+1)-pf[r1]+pf[l1-1]+f[i];
//cerr<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<l3<<" "<<r3<<'\n';
add3[l3].pb(cost);
del3[r3].pb(cost);
}
}
return f[n];
}
