#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];
int prv[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();
}
}
prv[1] = 1;
pref[1] = pos[1];
for (int i = 2; i <= n; i++) {
pref[i] = pref[i - 1] + pos[i];
if (col[i] != col[i - 1]) {
prv[i] = i;
}
else {
prv[i] = prv[i - 1];
}
}
for (int i = 1; i <= n; i++) {
dp[i] = inf;
if (prv[i] == 1) {
continue;
}
for (int j = prv[prv[i] - 1]; j <= prv[i] - 1; j++) {
long long dist_l = pref[prv[i] - 1] - pref[j - 1];
long long dist_r = pref[i] - pref[prv[i] - 1];
long long sum = dist_r - dist_l;
if (prv[i] - j >= i - prv[i] + 1) {
sum += 1LL * pos[prv[i]] * (prv[i] - j - (i - prv[i] + 1));
}
else {
sum -= 1LL * pos[prv[i] - 1] * ((i - prv[i] + 1) - (prv[i] - j));
}
assert(sum > 0);
dp[i] = min(dp[i], dp[j - 1] + sum);
}
}
return dp[n];
}
