#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();
if (r[n-1] < b[0]) { // Subtask 2
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;
} else if (n <= 200 && m <= 200) {
vector<vector<ll>> dp(n+1, vector<ll>(m+1));
for (int i = 1; i <= n; i++) dp[i][0] = LLONG_MAX;
for (int i = 1; i <= m; i++) dp[0][i] = LLONG_MAX;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = abs(r[i-1]-b[j-1]) + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));
// cout << i << " " << j << " " << dp[i][j] << endl;
}
}
return dp[n][m];
}
// n = 19;
// 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]) {
end++;
i++;
}
for ( ; i < n+m; i++) {
for (int j = start; j < end; j++) {
if ((j > 0 && dp[j-1] != LLONG_MAX) || (j == 0)) {
dp[i] = min(dp[i], (j > 0 ? dp[j-1] : 0) +cost(j, i));
}
if (dp[j] != LLONG_MAX) dp[i] = min(dp[j] +cost(j, i), dp[i]);
}
// cout << i << " " << start << " " << end << endl;
if (i < n+m-1 && bits[i] != bits[i+1]) {
start = end;
end = i+1;
}
// cout << dp[i] << endl;
}
// cout << dp[36] << endl;
return dp[n+m-1];
}
