// In the name of Allah
#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = (1 << 18) + 4;
const ll oo = 1e18 + 4;
int n; vector<pll> A; vector<pii> ls;
ll dp[maxn]; vector<int> ls0, ls1;
pll t[2 * maxn]; ll valx[maxn];
void build(int v, int tl, int tr) {
t[v].F = 0;
if (tr - tl == 1) {
t[v].S = valx[tl];
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v].S = min(t[2 * v + 1].S, t[2 * v + 2].S) + t[v].F;
}
void add_val(int v, int tl, int tr, int l, int r, ll x) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl || r <= l) return ;
if (l == tl && r == tr) {
t[v].F += x; t[v].S += x;
return ;
}
int mid = (tl + tr) / 2;
add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
t[v].S = min(t[2 * v + 1].S, t[2 * v + 2].S) + t[v].F;
}
ll calx(int l, int r) {
ls0.clear(); ls1.clear();
for (int i = l; i < r; i++) {
if (A[i].S == 0) ls0.pb(i);
else ls1.pb(i);
}
if (len(ls0) == 0 || len(ls1) == 0) return oo;
if (ls0[0] > ls1[0]) swap(ls0, ls1);
reverse(all(ls1));
while (len(ls0) < len(ls1)) ls0.pb(ls0.back());
while (len(ls1) < len(ls0)) ls1.pb(ls1.back());
ll res = 0;
for (int i = 0; i < len(ls0); i++) res += (A[ls1[i]].F - A[ls0[i]].F);
return res;
}
ll min_total_length(vector<int> rx, vector<int> bx) {
n = len(rx) + len(bx); A.pb(Mp(-1, -1));
for (int i = 0; i < len(rx); i++) A.pb(Mp(rx[i], 0));
for (int i = 0; i < len(bx); i++) A.pb(Mp(bx[i], 1));
sort(all(A));
int j = 1;
for (int i = 1; i <= n; i++) {
if (A[i].S != A[j].S) {
ls.pb(Mp(j, i));
j = i;
}
}
ls.pb(Mp(j, n + 1));
fill(dp, dp + (n + 1), oo); dp[0] = 0;
for (int d = 1; d < len(ls); d++) {
int l = ls[d].F, r = ls[d].S;
int lx = ls[d - 1].F, rx = ls[d - 1].S;
ll sm = 0;
for (int j = rx - 1; j >= lx; j--) {
sm += abs(A[j].F - A[l].F);
valx[j] = min(dp[j], dp[j - 1]) + sm;
}
build(0, lx, rx);
for (int i = l; i < r; i++) {
dp[i] = t[0].S;
if (i + 1 < r) {
int jx = (i - l) + 1;
ll R1 = abs(A[i + 1].F - A[rx - 1].F);
ll R2 = abs(A[i + 1].F - A[l].F);
add_val(0, lx, rx, rx - jx, rx, R1);
add_val(0, lx, rx, lx, rx - jx, R2);
}
}
}
return dp[n];
}
