#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXM 100005
#define INF (ll)2e18
ll dp[MAXN+MAXM];
vector<pair<ll,int>> points;//(position,type), r=0, b=1
ll st[4*MAXN];//dp+cost rmq
ll lazy[4*MAXN];
int pos;
int size_seg;
int m;
int prev_col;
ll suff[MAXN];
void build(int v=1,int start=1,int end=size_seg){
lazy[v]=0;
if(start==end){
int n=start;
st[v]=dp[pos-1-n]+n*points[pos].first-suff[n];//pos is the first of new segment
return;
}
int mid=(start+end)/2;
build(2*v,start,mid);
build(2*v+1,mid+1,end);
st[v]=min(st[2*v],st[2*v+1]);
}
void update(int from,int to,ll val,int v=1,int start=1,int end=size_seg){
if(start==from&&end==to){
st[v]+=val;
lazy[v]+=val;
return;
}
int mid=(start+end)/2;
if(lazy[v]){//propagate
update(start,mid,lazy[v],2*v,start,mid);
update(mid+1,end,lazy[v],2*v+1,mid+1,end);
lazy[v]=0;
}
if(to<=mid){
update(from,to,val,2*v,start,mid);
}else if(from>mid){
update(from,to,val,2*v+1,mid+1,end);
}else{
update(from,mid,val,2*v,start,mid);
update(mid+1,to,val,2*v+1,mid+1,end);
}
st[v]=min(st[2*v],st[2*v+1]);
}
ll min_total_length(vector<int> r, vector<int> b) {
points.clear();
points.push_back({-1,-1});//numbering from 1, fake point
//merge sort
reverse(r.begin(),r.end());
reverse(b.begin(),b.end());
while(!r.empty()||!b.empty()){
if((!r.empty())&&(!b.empty())){
if(r.back()<b.back()){
points.push_back({r.back(),0});
r.pop_back();
}else{
points.push_back({b.back(),1});
b.pop_back();
}
}else if(r.empty()){
points.push_back({b.back(),1});
b.pop_back();
}else{
points.push_back({r.back(),0});
r.pop_back();
}
}
dp[0]=0;
pos=1;
m=1;
while(pos==1||prev_col==points[pos].second){
if(pos==1) prev_col=points[pos].second;
dp[pos]=INF;
pos++;
m++;
}//found first new segment
for(;pos<points.size();pos++,m++){
if(prev_col!=points[pos].second){
//entered new segment
prev_col=points[pos].second;
size_seg=m-1;
m=1;
suff[0]=0;
for(int i=1;i<=size_seg;i++){
suff[i]=suff[i-1]+points[pos-i].first;
}
build();
}else{
//existing segment,st needs update
if(m<=size_seg) update(m,size_seg,points[pos].first-points[pos-m+1].first);
update(1,min(m-1,size_seg),points[pos].first-points[pos-m].first);
}
dp[pos]=st[1];
}
return dp[points.size()-1];
}
