#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e18;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
struct pt {
int x;
bool col;
};
vector<pt> pts;
while(!r.empty() or !b.empty()) {
if(!r.empty() and (b.empty() or r.back()>b.back())) {
pts.push_back({r.back(),1});
r.pop_back();
} else {
pts.push_back({b.back(),0});
b.pop_back();
}
}
reverse(all(pts));
int n = pts.size();
pts.insert(pts.begin(),{0,0});
vector<ll> pref(n+2);
for(int i=0;i<=n;++i) {
pref[i+1]=pref[i]+pts[i].x;
}
vector<ll> dp(n+1,oo);
dp[0]=0;
auto cost = [&](int a, int b, int c) {
int bal = (b-a)-(c-b);
ll tmp=0;
if(bal>0) tmp = (ll)pts[b].x*bal;
else tmp = (ll)pts[b-1].x*bal;
return tmp + min(dp[a],dp[a-1]) + pref[c] - pref[b] - (pref[b]-pref[a]);
};
int last=-1;
for(int i=1;i<=n;) {
int j=i;
while(j<=n and pts[i].col==pts[j].col)
++j;
if(last!=-1) {
for(int k=j;k>i;--k) {
while(last<i-1 and cost(last+1,i,k)<cost(last,i,k)) {
++last;
}
// for(int o=last;o<i;++o) dp[k-1] =min(dp[k-1],cost(o,i,k));
dp[k-1] =min(dp[k-1],cost(last,i,k));
}
}
last = i;
i=j;
}
return dp[n];
}
