#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;
ll pref[MAXN+MAXM];
ll solve(ll l,ll r,ll f){
return (pref[r]-pref[f-1])-(pref[f-1]-pref[l-1])+(f-l)*points[f-1].first-(r-f+1)*points[f].first+max(f-l,r-f+1)*(points[f].first-points[f-1].first);
}
ll solve2(int p,int n,int m_){
return solve(p-m_-n+1,p,p-m_+1);
}
void build(int v=1,int start=1,int end=size_seg){
lazy[v]=0;
if(start==end){
ll n=start;
st[v]=min(dp[pos-m-n],dp[pos-m-n+1])+solve2(pos,n,m);//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();
}
}
pref[0]=0;
for(int i=1;i<points.size();i++){
assert(points[i].first>=points[i-1].first);
pref[i]=pref[i-1]+points[i].first;
}
dp[0]=0;
pos=1;
m=1;
while(pos==1||points[pos-1].second==points[pos].second){
dp[pos]=INF;
pos++;
m++;
}//found first new segment
for(;pos<points.size();pos++,m++){
if(points[pos-1].second!=points[pos].second){
//entered new segment
size_seg=m-1;
m=1;
build();
}else{
//existing segment,st needs update
/*
for(int n=1;n<=size_seg;n++){
ll dif=solve2(pos,n,m)-solve2(pos-1,n,m-1);
if(n>=m){
assert(dif==(points[pos].first-points[pos-m+1].first));
}else{
assert(dif==(points[pos].first-points[pos-m].first));
}
}
*/
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);
}
/*
ll ans=INF;
for(int n=1;n<=size_seg;n++){
ans=min(ans,min(dp[pos-m-n],dp[pos-m-n+1])+solve2(pos,n,m));
}
*/
dp[pos]=st[1];
//dp[pos]=ans;
}
return dp[points.size()-1];
}
