#include "wiring.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
int inf = numeric_limits<int>::max() / 2;
i64 min_total_length(vector<int> r, vector<int> b) {
const int R = r.size();
const int B = b.size();
vector<int> Rv, Bv;
Rv.emplace_back(-inf);
Bv.emplace_back(-inf);
copy(iterall(r), back_inserter(Rv));
copy(iterall(b), back_inserter(Bv));
Rv.emplace_back(inf);
Bv.emplace_back(inf);
vector<pair<int, bool>> seq;
for (auto el : r) seq.emplace_back(el, true);
for (auto el : b) seq.emplace_back(el, false);
sort(iterall(seq), [](auto l, auto r) { return l.first < r.first; });
int n = 1;
vector<int> rhm(1), bhm(1);
vector<i64> rs(1), bs(1);
for (auto [el, clr] : seq) {
if (clr)
rhm.emplace_back(1);
else
rhm.emplace_back(0);
if (!clr)
bhm.emplace_back(1);
else
bhm.emplace_back(0);
if (clr)
rs.emplace_back(el);
else
rs.emplace_back(0);
if (!clr)
bs.emplace_back(el);
else
bs.emplace_back(0);
rhm[n] += rhm[n - 1];
bhm[n] += bhm[n - 1];
rs[n] += rs[n - 1];
bs[n] += bs[n - 1];
++n;
}
map<int, int> hmInterval;
vector<i64> dp(R + B);
hmInterval[0] = -1;
for (int i = 0; i < R + B; i++) {
auto [el, clr] = seq[i];
i64 d;
if (clr) {
auto it = lower_bound(iterall(Bv), el);
d = min(*it - el, el - *prev(it));
} else {
auto it = lower_bound(iterall(Rv), el);
d = min(*it - el, el - *prev(it));
}
dp[i] = (i ? dp[i - 1] : 0) + d;
auto it = hmInterval.find(rhm[i + 1] - bhm[i + 1]);
if (it != hmInterval.end()) {
auto j = it->second;
dp[i] = min(dp[i], dp[j] + abs(rs[i + 1] - rs[j + 1] - bs[i + 1] +
bs[j + 1]));
}
hmInterval[rhm[i + 1] - bhm[i + 1]] = i;
}
return dp.back();
}
