// wiring.cpp
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define red 1
#define blue 0
const int N = 200010;
long long seg[4 * N], lazy[4 * N], dp[N];
vector<pair<int,bool>> v;
int n, nxt[N];
long long getmin(int s, int e, int idx, int l, int r) {
if (s > r || e < l) return 1e18;
if (s >= l && e <= r) return seg[idx] + lazy[idx];
lazy[idx * 2] += lazy[idx];
lazy[idx * 2 + 1] += lazy[idx];
seg[idx] += lazy[idx];
lazy[idx] = 0;
return min(getmin(s, (s + e) / 2, idx * 2, l, r), getmin((s + e) / 2 + 1, e, idx * 2 + 1, l, r));
}
long long update(int s, int e, int idx, int l, int r, long long val) {
if (s > r || e < l) return seg[idx] + lazy[idx];
if (s >= l && e <= r) {
lazy[idx] += val;
return seg[idx] + lazy[idx];
}
lazy[idx * 2] += lazy[idx];
lazy[idx * 2 + 1] += lazy[idx];
lazy[idx] = 0;
return seg[idx] = min(update(s, (s + e) / 2, idx * 2, l, r, val),
update((s + e) / 2 + 1, e, idx * 2 + 1, l, r, val));
}
long long min_total_length(vector<int> r, vector<int> b) {
int j = 0;
for (int i = 0; i < r.size(); i++) {
while (j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++], blue));
v.push_back(make_pair(r[i], red));
}
while (j < b.size()) v.push_back(make_pair(b[j++], blue));
n = v.size();
nxt[n] = n;
for (int i = n - 1; i >= 0; i--) {
if (v[i].second != v[i + 1].second) nxt[i] = i + 1;
else nxt[i] = nxt[i + 1];
}
for (int i = n - 1; i >= 0; i--) {
if (nxt[i] == n) {
dp[i] = 1e18;
update(0, n, 1, i, i, dp[i]);
continue;
}
dp[i] = 1e18;
if (nxt[i] == i + 1) {
long long sum = 0;
for (int j = i + 1; j < nxt[i + 1]; j++) {
update(0, n, 1, j, j, -getmin(0, n, 1, j, j));
update(0, n, 1, j, j, sum + dp[j]);
sum += v[j].first - v[i].first;
}
for (int j = nxt[i + 1]; j <= nxt[nxt[i + 1]]; j++) {
update(0, n, 1, j, j, -getmin(0, n, 1, j, j));
update(0, n, 1, j, j, dp[j] + sum);
if (j < nxt[nxt[i + 1]]) sum += v[j].first - v[i + 1].first;
}
dp[i] = min(dp[i], getmin(0, n, 1, i + 2, nxt[nxt[i + 1]]));
update(0, n - 1, 1, i, i, dp[i]);
} else {
int cur = nxt[i];
int cur2 = nxt[cur] - 1;
int num = cur - i;
long long s = 0;
if (cur2 - cur < num) {
if (cur + 1 <= cur2) update(0, n, 1, cur + 1, cur2, v[cur].first - v[i].first);
} else {
update(0, n, 1, cur + 1, cur + num - 1, v[cur].first - v[i].first);
if (cur + num <= cur2) {
update(0, n, 1, cur + num, cur2, v[cur - 1].first - v[i].first);
}
}
cur2++;
if (cur2 - cur < num) s = v[cur].first - v[i].first;
else s = v[cur - 1].first - v[i].first;
update(0, n, 1, cur2, nxt[cur2], s);
dp[i] = getmin(0, n, 1, cur + 1, nxt[cur2]);
update(0, n, 1, i, i, dp[i]);
}
}
return dp[0];
}
