#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
const long long INF = 1e18;
const int nax = 1e5 + 2;
vector<int>pos;
vector<int>type;
int upto[nax * 2];
template<const int N> struct segmentTree {
long long st[N * 4];
segmentTree() {
fill(st, st+N*4, INF);
}
void update(int l, int r, int pos, long long val, int v) {
if(l==r) {
st[v] = val;
return;
}
int mid = (l+r)/2;
if(pos<=mid) update(l, mid, pos, val, v*2);
else update(mid+1, r, pos, val, v*2+1);
st[v] = min(st[v*2], st[v*2+1]);
}
long long query(int l, int r, int L, int R, int v) {
if(l>=L && r<=R) return st[v];
if(l>R || r<L) return INF;
int mid = (l+r)/2;
return min(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+1));
}
}; segmentTree<nax * 2>lefBig, lefSmall;
long long min_total_length(vector<int> r, vector<int> b) {
int p0 = 0, p1 = 0;
int n = r.size(), m = b.size();
while(p0<n || p1<m) {
if(p0<n && p1<m) {
if(r[p0]<b[p1]) {
pos.push_back(r[p0]);
type.push_back(0);
++p0;
} else {
pos.push_back(b[p1]);
type.push_back(1);
++p1;
}
} else if(p0<n) {
pos.push_back(r[p0]);
type.push_back(0);
++p0;
} else {
pos.push_back(b[p1]);
type.push_back(1);
++p1;
}
}
fill(upto, upto+nax*2, n+m-1);
long long rit1[n+m], rit2[n+m], lef1[n+m], lef2[n+m];
for(int i=0; i<n+m; ++i) {
int j = i;
while(j+1<n+m && type[j+1]==type[i]) ++j;
int pt = j;
long long cr = 0;
while(j>=i) cr += pos[pt] - pos[j], rit1[j] = cr, upto[j] = pt, --j;
j = pt;
cr = 0;
while(j>=i) {
cr += (pt+1<n+m) ? pos[pt+1] - pos[j] : INF;
cr = min(cr, INF);
rit2[j] = cr;
--j;
}
i = pt;
}
for(int i=n+m-1; i>=0; --i) {
int j = i;
while(j-1>=0 && type[j-1]==type[i]) --j;
int pt = j;
long long cr = 0;
while(j<=i) cr += pos[j] - pos[pt], lef1[j] = cr, ++j;
cr = 0;
j = pt;
while(j<=i) {
cr += (pt-1>=0) ? pos[j] - pos[pt-1] : INF;
cr = min(cr, INF);
lef2[j] = cr;
++j;
}
i = pt;
}
lefBig.update(1, n+m, n+m, lef1[n+m-1], 1);
lefSmall.update(1, n+m, n+m, lef2[n+m-1], 1);
vector<long long>dp(n+m, INF);
for(int i=n+m-1; i>=0; --i) {
if(upto[i]==n+m-1) continue;
int leflen = upto[i] - i + 1;
int j = upto[i] + leflen;
j = (upto[i]==n+m-1) ? n+m : min(j, upto[upto[i]+1]);
dp[i] = rit2[i] + lefBig.query(1, n+m, upto[i]+2, j+1, 1);
int k = min(n+m, upto[upto[i]+1]);
dp[i] = min(dp[i], rit1[i] + lefSmall.query(1, n+m, j+2, k+1, 1));
if(i) {
lefBig.update(1, n+m, i+1, min(INF, min(dp[i], dp[i+1]) + lef1[i]), 1);
lefSmall.update(1, n+m, i+1, min(INF, min(dp[i], dp[i+1]) + lef2[i]), 1);
}
}
return dp[0];
}
