#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
vi mapper, bits;
ll cost(int i, int j) {
vi r, b;
for (int k = i; k <= j; k++) {
if (bits[k] != bits[i]) b.push_back(mapper[k]);
else r.push_back(mapper[k]);
}
int n = r.size(), m = b.size();
// for (int k = 0; k < n; k++) {
// cout << r[k] << " ";
// }
// cout << endl;
// for (int k = 0; k < m; k++) {
// cout << b[k] << " ";
// }
// cout << endl;
ll res = 0;
if (n <= m) {
int idx = n-1;
for (int i = 0; i < m; i++) {
if (idx < 0) res += b[i]-r[n-1];
else {
res += b[i]-r[idx];
idx--;
}
}
} else {
int idx = m-1;
for (int i = 0; i < n; i++) {
if (idx < 0) res += b[0]-r[i];
else {
res += b[idx]-r[i];
idx--;
}
}
}
return res;
}
ll min_total_length(vi r, vi b) {
int n = r.size(), m = b.size();
// 0 Red 1 Blue
bits = vi(n+m);
mapper = vi(n+m);
int idxR = 0, idxB = 0;
while (idxR < n || idxB < m) {
if (idxR < n && idxB < m) {
bits[idxR+idxB] = (r[idxR] > b[idxB]);
mapper[idxR+idxB] = min(r[idxR], b[idxB]);
if (r[idxR] < b[idxB]) idxR++;
else idxB++;
} else if (idxR < n) {
bits[idxR+idxB] = 0;
mapper[idxR+idxB] = r[idxR];
idxR++;
} else {
bits[idxR+idxB] = 1;
mapper[idxR+idxB] = b[idxB];
idxB++;
}
}
vector<ll> dp(n+m, LLONG_MAX);
int start = 0, end = 0, i = 0;
while (bits[i] == bits[0]) {
dp[i] = 0;
end++;
i++;
}
for ( ; i < n+m; i++) {
for (int j = start; j < end; j++) {
dp[i] = min(dp[i], dp[j-1]+cost(j, i));
// cout << j << " " << i << " " << dp[i] << endl;
}
if (i < n+m-1 && bits[i] != bits[i+1]) {
start = end;
end = i+1;
}
}
return dp[n+m-1];
}
