#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int N = 200010;
const int INF = 2e9+2;
int sz[N];
ll dp[N], qsl[N], qsr[N];
ll min_total_length(vector<int> R, vector<int> B)
{
vector<pii> all;
for (auto x : R) all.emplace_back(x, 0);
for (auto x : B) all.emplace_back(x, 1);
int n = all.size();
all.emplace_back(-1, -1);
sort(all.begin(), all.end());
R.insert(R.begin(), -INF);
R.insert(R.end(), INF);
B.insert(B.begin(), -INF);
B.insert(B.end(), INF);
int z = 0;
for (int i = 1; i <= n; ++i) {
if (all[i].second != all[i-1].second) z = 0;
sz[i] = ++z;
}
for (int i = 1; i <= n; ++i)
qsl[i] = qsl[i-1] + all[i].first;
for (int i = n; i >= 1; --i)
qsr[i] = qsr[i+1] + (INF-all[i].first);
for (int i = 1; i <= n; ++i) {
ll nl, nr; // nearest opposite color of all[i].second to the left and to the right
if (all[i].second == 0) {
nl = *(lower_bound(B.begin(), B.end(), all[i].first)-1);
nr = *lower_bound(B.begin(), B.end(), all[i].first);
} else {
nl = *(lower_bound(R.begin(), R.end(), all[i].first)-1);
nr = *lower_bound(R.begin(), R.end(), all[i].first);
}
dp[i] = dp[i-1]+min(all[i].first-nl, nr-all[i].first);
ll j = -1; // from j to i there will be one color followed by another color with equal amount
if (sz[i-sz[i]] >= sz[i]) j = i-sz[i]-sz[i]+1;
if (j != -1) {
ll ml = (i+j)/2;
ll mr = (i+j+1)/2;
ll c = i-ml;
ll cl = (all[ml].first*1ll*c) - (qsl[ml]-qsl[j-1]);
ll cr = (INF-all[mr].first)*1ll*c - (qsr[mr]-qsr[i+1]);
ll cm = (all[mr].first-all[ml].first)*c;
dp[i] = min(dp[i], cl+cr+cm+dp[j-1]);
}
}
return dp[n];
}
