#include "bits/stdc++.h"
using namespace std;
#include "wiring.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
const int N = 2e5 + 5;
const ll inf = 1e14;
ll c[N], a[N], is[N];
ll dp[N], pref[N];
ll min_total_length(vector<int> r, vector<int> b) {
int n = (int)r.size();
int m = (int)b.size();
int T = n + m;
reverse(r.begin(), r.end());
reverse(b.begin(), b.end());
for(int i=1;i<=T;i++){
if(b.empty()) a[i] = r.back(), r.pop_back();
else if(r.empty()) a[i] = b.back(), b.pop_back(), c[i] = 1;
else if(r.back() < b.back()) a[i] = r.back(), r.pop_back();
else a[i] = b.back(), b.pop_back(), c[i] = 1;
pref[i] = pref[i-1] + a[i];
}
ar<ll, 2> last {-1, -1};
is[0] = 1;
c[0] = -1;
set<ar<ll, 2>> L, R;
ll z = 0;
for(int i=1;i<=T;i++){
dp[i] = inf;
if(is[i - 1] && ~last[c[i] ^ 1]) is[i] = 1, dp[i] = dp[i - 1] + a[i] - last[c[i] ^ 1];
if(c[i] != c[i - 1] && ~c[i - 1]){
z = i - 1;
L.clear(), R.clear();
for(int j=i-2;~j;j--){
if(c[j + 1] == c[i]) break;
if(is[j]){
dp[i] = min(dp[i], dp[j] + a[i] * (i - j) - pref[i] + pref[j]);
if(2 * z - i <= j){
R.insert({pref[j] - a[z] * j + dp[j], j});
} else {
L.insert({pref[j] - a[z + 1] * j + dp[j], j});
}
}
}
} else if(z && !L.empty()){
int j = 2 * z - i;
if(is[j]){
L.erase({pref[j] - a[z + 1] * j + dp[j], j});
R.insert({pref[j] - a[z] * j + dp[j], j});
}
}
last[c[i]] = a[i];
if(!R.empty()) is[i] = 1, dp[i] = min(dp[i], (*R.begin())[0] + pref[i] - pref[z] * 2 - a[z] * (i - 2 * z));
if(!L.empty()) is[i] = 1, dp[i] = min(dp[i], (*L.begin())[0] + pref[i] - pref[z] * 2 + a[z + 1] * (2 * z - i));
}
//~ for(int i=1;i<=T;i++) cout<<a[i]<<" ";
//~ cout<<"\n";
//~ for(int i=1;i<=T;i++) cout<<c[i]<<" ";
//~ cout<<"\n";
//~ for(int i=1;i<=T;i++) cout<<dp[i]<<" ";
//~ cout<<"\n";
return dp[T];
}
/*
4 5
1 2 3 7
0 4 5 9 10
1 2
0 2
1
*/
