#include "wiring.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e17;
ll min_total_length(vector<int> r, vector<int> b){
vector<vector<ll>> v;
int prev = -1;
for(auto i = r.begin(), j = b.begin(); i != r.end() || j != b.end();){
if(j == b.end() || (i != r.end() && *i < *j)){
if(prev != 0) v.pb({});
prev = 0;
v.back().pb(*i);
i++;
}
else{
if(prev != 1) v.pb({});
prev = 1;
v.back().pb(*j);
j++;
}
}
int n = v.size();
vector<vector<ll>> dp(n), pref(n), suff(n);
vector<vector<ll>> mn1(n);
for(int i = n-1; i >= 0; i--){
int m = v[i].size();
dp[i].assign(m, inf), pref[i].resize(m, 0), suff[i].resize(m, 0);
mn1[i].assign(m, inf);
for(int j = 0; j < m; j++){
if(j) pref[i][j] = pref[i][j-1];
pref[i][j]+=v[i][j];
}
for(int j = m-1; j >= 0; j--){
if(j != m-1) suff[i][j] = suff[i][j+1];
suff[i][j]+=v[i][j];
}
int k = v[i+1].size();
for(int j = m-1; j >= 0; j--){
if(i == n-1) continue;
dp[i][j] = min(dp[i][j], v[i+1][0]*(m-j)-suff[i][j]+dp[i+1][0]);
ll x = -suff[i][j];
if(m-j-1 < k) x+=mn1[i+1][m-j-1]-(k-m+j)*v[i+1][0];
else x+=mn1[i+1].back()+(m-j-k)*v[i+1][0];
dp[i][j] = min(dp[i][j], x);
for(int l = 0; l < k; l++){
ll cur = pref[i+1][l]-suff[i][j];
if(m-j > l+1) continue; //cur+=v[i+1][0]*(m-j-l-1);
else cur-=v[i][m-1]*(l+1-m+j);
if(i+1 == n-1 && l == k-1) dp[i][j] = min(dp[i][j], cur);
else if(l == k-1) dp[i][j] = min(dp[i][j], cur+dp[i+2][0]);
else dp[i][j] = min(dp[i][j], cur+dp[i+1][l+1]);
}
}
for(int j = 0; j < m; j++){
if(j) mn1[i][j] = mn1[i][j-1];
ll cur = pref[i][j]+v[i][0]*(m-j-1);
if(i == n-1 && j == m-1) mn1[i][j] = min(mn1[i][j], cur);
else if(j == m-1) mn1[i][j] = min(mn1[i][j], cur+dp[i+1][0]);
else mn1[i][j] = min(mn1[i][j], cur+dp[i][j+1]);
}
}
return dp[0][0];
}
