#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
i64 inf = numeric_limits<i64>::max() / 3;
i64 min_total_length(vector<int> r, vector<int> b) {
const int R = r.size();
const int B = b.size();
vector<i64> 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<i64, bool>> seq;
transform(iterall(r), back_inserter(seq),
[](int x) -> decltype(seq)::value_type {
return {x, true};
});
transform(iterall(b), back_inserter(seq),
[](int x) -> decltype(seq)::value_type {
return {x, false};
});
sort(iterall(seq),
[](decltype(seq)::value_type l, decltype(seq)::value_type r) {
return l.first < r.first;
});
int n = 1;
vector<int> rhm(1, 0), bhm(1, 0);
vector<i64> rs(1, 0), bs(1, 0);
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 > 0 ? 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],
(j >= 0 ? dp[j] : 0) +
abs(rs[i + 1] - rs[j + 1] - bs[i + 1] + bs[j + 1]));
}
hmInterval[rhm[i + 1] - bhm[i + 1]] = i;
}
return dp.back();
}
