// AM + DG
#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
ll compute_cost_old(ll l, ll r, const vpll& p) {
ll ans = 0ll;
ll pref_color = p[l].se;
ll fdiff = l;
while(fdiff <= r && p[fdiff].se == pref_color) fdiff++;
assert(fdiff <= r);
for(ll i = l; i < fdiff; i++) {
ans -= p[i].fi;
}
for(ll i = fdiff; i <= r; i++) {
ans += p[i].fi;
}
ll n = fdiff - l;
ll m = r - fdiff + 1ll;
ans += abs(n - m) * (m > n ? -p[fdiff - 1ll].fi : p[fdiff].fi);
return ans;
}
ll compute_cost(ll ls, ll rs, ll lsum, ll rsum, ll lend, ll rstart) {
// cout << ls << " " << rs << " " << lsum << " " << rsum << " " << lend << " " << rstart << "\n";
ll ans = 0ll;
ans -= lsum;
ans += rsum;
ans += abs(ls - rs) * (rs > ls ? -lend : rstart);
return ans;
}
ll min_total_length(vi r, vi b) {
vpll p;
int rs = r.size(), bs = b.size();
int ri = 0, bi = 0;
while(ri < rs && bi < bs) {
if(r[ri] < b[bi]) {
p.pb({r[ri], 0});
ri++;
} else {
p.pb({b[bi], 1});
bi++;
}
}
while(ri < rs) {
p.pb({r[ri], 0});
ri++;
}
while(bi < bs) {
p.pb({b[bi], 1});
bi++;
}
ll MAX_DP = rs + bs;
const ll inf = 1'000'000'000'000ll;
vll dp(MAX_DP, inf);
ll l_ind = 0ll, r_ind = -1ll, opt_split = 0ll, lsum = 0ll, rsum = 0ll;
for(ll i = 1ll; i < MAX_DP; i++) {
ll cur_color = p[i].se;
ll j = i;
if(cur_color != p[i - 1ll].se) {
while(j >= 0 && p[j].se == cur_color) j--;
r_ind = j;
opt_split = j; /*Opt split has to be in [l_ind - 1, r_ind - 1]*/
lsum = p[opt_split].fi;
rsum = p[i].fi;
opt_split--;
while(j >= 0 && p[j].se != cur_color) j--;
l_ind = j + 1ll;
if(l_ind == 0ll) { // ! YOU ACCIDENTALLY WROTE l_ind = 0 bro
for(ll k = 0ll; k <= opt_split; k++) {
lsum += p[k].fi;
}
}
} else {
rsum += p[i].fi;
}
if(r_ind == -1ll) {
dp[i] = inf;
} else if(l_ind == 0ll) {
dp[i] = compute_cost(r_ind - l_ind + 1ll, i - r_ind, lsum, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
} else if(l_ind == r_ind) {
ll min_recurs = min(dp[l_ind], (l_ind > 0ll ? dp[l_ind - 1ll] : 0ll));
dp[i] = min_recurs + compute_cost(r_ind - l_ind + 1ll, i - r_ind, lsum, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
} else {
ll cur_cost = dp[opt_split] + compute_cost(r_ind - opt_split, i - r_ind, lsum, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
while(opt_split >= l_ind) {
ll pot_cost = dp[opt_split - 1ll] + compute_cost(r_ind - opt_split + 1ll, i - r_ind, lsum + p[opt_split].fi, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
// cout << "SPLIT " << opt_split << " " << cur_cost << " " << pot_cost << "\n";
if(pot_cost < cur_cost) {
cur_cost = pot_cost;
lsum += p[opt_split].fi;
opt_split--;
} else {
break;
}
}
dp[i] = cur_cost;
}
// cout << dp[i] << " " << p[i].fi << " " << p[i].se << ", l = " << l_ind << " , r = " << r_ind << "\n";
}
return dp[MAX_DP - 1ll];
}
