#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
const int maxn = 2e5 + 20;
int pos[maxn];
int col[maxn];
long long dp[maxn];
long long pref[maxn];
long long suf[maxn];
long long min_total_length(vector<int> r, vector<int> b) {
int n = r.size();
int m = b.size();
if (r[n - 1] < b[0]) {
long long res = 0;
for (int i = 0; i < n; i++) {
res -= r[i];
}
for (int i = 0; i < m; i++) {
res += b[i];
}
if (n > m) {
res += 1LL * b[0] * (n - m);
}
else {
res -= 1LL * r[n - 1] * (m - n);
}
return res;
}
n = n + m;
for (int i = n; i >= 1; i--) {
if (!r.empty() && (b.empty() || r.back() > b.back())) {
pos[i] = r.back();
col[i] = 0;
r.pop_back();
}
else {
pos[i] = b.back();
col[i] = 1;
b.pop_back();
}
}
dp[0] = 0;
col[0] = -1;
col[n + 1] = -1;
for (int i = 1; i <= n; i++) {
dp[i] = inf;
}
for (int i = 2; i <= n; i++) {
if (col[i] == col[i - 1]) {
continue;
}
int lt = i - 1;
for (; col[lt] == col[i - 1]; lt--) {
pref[lt] = pref[lt + 1] - pos[lt] + pos[i];
suf[lt] = suf[lt + 1] - pos[lt] + pos[i - 1];
}
lt++;
for (int j = lt; j <= i; j++) {
pref[j] += min(dp[j], dp[j - 1]);
suf[j] += min(dp[j], dp[j - 1]);
}
for (int j = lt + 1; j <= i - 1; j++) {
pref[j] = min(pref[j], pref[j - 1]);
}
for (int j = i - 2; j >= lt; j--) {
suf[j] = min(suf[j], suf[j + 1]);
}
int rt = i;
long long sum = 0;
for (; col[rt] == col[i]; rt++) {
sum += pos[rt];
if (rt - i + 1 < i - lt) {
dp[rt] = sum + min(suf[i - (rt - i + 1)] - 1LL * pos[i - 1] * (rt - i + 1), pref[i - (rt - i + 1)] - 1LL * pos[i] * (rt - i + 1));
}
else {
dp[rt] = sum + suf[lt] - 1LL * pos[i - 1] * (rt - i + 1);
}
}
}
return dp[n];
}
