#include "wiring.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 200005;
LL seg[2][4*N], dp[N], FF[N], ff[N], BB[N], bb[N], pos[N];
int col[N], last[N], cnt;
int n;
void add(LL val, int idx, int t, int l = 1, int r = n, int now = 1){
if(l==r){
seg[t][now] = val;
return ;
}
int m = (l+r)>>1;
if(idx <= m) add(val, idx, t, l, m, now<<1);
else add(val, idx, t, m+1, r, now<<1|1);
seg[t][now] = min(seg[t][now<<1], seg[t][now<<1|1]);
}
LL get(int ll, int rr, int t, int l = 1, int r = n, int now = 1){
if(ll > rr || l > rr || r < ll) return 1e18;
if(l >= ll && r <= rr) return seg[t][now];
int m = (l+r)>>1;
return min( get(ll, rr, t, l, m, now<<1), get(ll, rr, t, m+1, r, now<<1|1));
}
long long min_total_length(vector<int> A, vector<int> B) {
n = SZ(A) + SZ(B);
int a, c, d, i, j, k, l = 0, r = 0;
while(l < SZ(A) && r < SZ(B)){
if(A[l] < B[r]){
pos[++cnt] = A[l++];
}else{
pos[++cnt] = B[r++];
col[cnt] = 1;
}
}
while(l < SZ(A)) pos[++cnt] = A[l++];
while(r < SZ(B)) pos[++cnt] = B[r++], col[cnt] = 1;
last[1] = 1;
for(i=2; i<=n; i++){
if(col[i] == col[i-1]) last[i] = last[i-1], FF[i] = FF[i-1], ff[i] = ff[i-1];
else last[i] = i;
FF[i] += pos[i] - pos[last[i]-1];
ff[i] += pos[i] - pos[last[i]];
}
l = n;
for(i = n-1; i>0; i--){
if(col[i] != col[i+1]) l = i+1;
else BB[i] = BB[i+1], bb[i] = bb[i+1];
BB[i] += pos[l] - pos[i];
bb[i] += pos[l-1] - pos[i];
}
for(i = 1; i <= n; i++){
dp[i] = 1e18;
// printf("xxxxxx%d %d : %d %lld %lld %lld %lld\n", pos[i], col[i], last[i], FF[i], ff[i], BB[i], bb[i]);
if(last[i] != 1){
d = i-last[i]+1;
l = last[last[i]-1];
// printf("##%d %d = %lld\n",max(l, last[i]-d), last[i]-1, get(max(l, last[i]-d), last[i]-1, 0));
dp[i] = min(dp[i], get(max(l, last[i]-d), last[i]-1, 0) + FF[i]);
dp[i] = min(dp[i], get(l, last[i]-d-1, 1) + ff[i]);
}
// printf("=====%lld %lld\n", min(dp[i-1],dp[i]) + bb[i], min(dp[i-1],dp[i]) + BB[i]);
add(min(dp[i-1],dp[i]) + bb[i], i, 0);
add(min(dp[i-1],dp[i]) + BB[i], i, 1);
// printf("i %d : %lld\n", i, dp[i]);
}
return dp[n];
}
/*
4 5
1 2 3 7
0 4 5 9 10
3 2
1 3 5
2 4
*/
