#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ind[200100],rt[200100],lft[200100],prf[200100],col[200100],pos[200100],dp[200100];
ll cst(int l,int r){
ll A=rt[l],B=lft[r];
return ((A-l+1)*pos[A]-prf[A]+prf[l-1]+prf[r]-prf[B]-(r-B)*pos[B])+(pos[B]-pos[A])*max(A-l+1,r-B+1);
}
void dnc(int l,int r,int opl,int opr){
if(!opl)return;
if(l>r)return;
int mid=l+r>>1,op=0;
for(int i=opl;i<=opr;i++){
ll K=min(dp[i-1],dp[i])+cst(i,mid);
if(K<dp[mid]) op=i,dp[mid]=K;}
dnc(l,mid-1,op,opr);
dnc(mid+1,r,opl,op);
}
ll min_total_length(std::vector<int> r, std::vector<int> b) {
int CC=0,n=r.size(),m=b.size();
r.push_back(2e9);
b.push_back(2e9);
int lpt=0,rpt=0;
for(int i=0;i<n+m;i++)
if(r[lpt]<b[rpt]) pos[CC]=prf[++CC]=r[lpt++];
else col[++CC]=1,pos[CC]=prf[CC]=b[rpt++];
for(int i=1;i<=CC;i++)
dp[i]=1e18;
int BEF=0,c=col[1];
int CC2=1;
ind[1]=lft[1]=1;
for(int i=2;i<=CC;i++){
prf[i]+=prf[i-1];
if(col[i]==c){
ind[i]=ind[i-1];
lft[i]=lft[i-1];
} else {
ind[i]=++CC2;
lft[i]=i;
for(int j=lft[i-1];j<i;j++)
rt[j]=i-1;
dnc(lft[i-1],rt[i-1],lft[BEF],rt[BEF]);
BEF=i-1,c=col[i];
}
}
dnc(lft[CC],CC,lft[BEF],rt[BEF]);
return dp[CC];
}
