#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
int N = r.size() + b.size();
int ridx = 0, bidx = 0;
vector<int> pos = {0}, col = {0};
while (ridx < r.size() || bidx < b.size()) {
if (bidx == b.size()) {
pos.push_back(r[ridx]);
col.push_back(0);
ridx++;
} else if (ridx == r.size()) {
pos.push_back(b[bidx]);
col.push_back(1);
bidx++;
} else if (r[ridx] < b[bidx]) {
pos.push_back(r[ridx]);
col.push_back(0);
ridx++;
} else {
pos.push_back(b[bidx]);
col.push_back(1);
bidx++;
}
}
vector<pair<int, int>> seg;
for (int i = 1; i <= N; ) {
int j = i;
while (j <= N && col[i] == col[j]) {
j++;
}
seg.push_back(make_pair(i, j - 1));
i = j;
}
vector<long long> pre(N + 1);
vector<long long> suf(N + 1);
for (int i = 0; i < seg.size(); i++) {
int lb = seg[i].first, rb = seg[i].second;
for (int j = rb - 1; j >= lb; j--) {
suf[j] = suf[j + 1] + (pos[rb] - pos[j]);
}
for (int j = lb + 1; j <= rb; j++) {
pre[j] = pre[j - 1] + (pos[j] - pos[lb]);
}
}
vector<long long> dp(N + 1, (long long)1e18);
dp[0] = 0;
for (int sid = 1; sid < seg.size(); sid++) {
int clb = seg[sid].first, crb = seg[sid].second;
int plb = seg[sid - 1].first, prb = seg[sid - 1].second;
for (int c = clb; c <= crb; c++) {
auto calc = [&] (int p) {
int psz = prb - p + 1;
int csz = c - clb + 1;
long long cost = 0;
cost += suf[p] + pre[c];
cost += (long long)(pos[clb] - pos[prb]) * max(psz, csz);
return min(dp[p - 1], dp[p]) + cost;
};
if (sid == 1) {
dp[c] = calc(plb);
} else {
int ll = plb, rr = prb + 1;
while (ll + 1 < rr) {
int mm = ll + (rr - ll) / 2;
if (calc(mm) - calc(mm - 1) < 0) {
ll = mm;
} else {
rr = mm;
}
}
dp[c] = calc(ll);
}
}
}
return dp[N];
}
