#include "wiring.h"
#include <bits/stdc++.h>
#define pb push_back
#define pos first
#define color second
#define ll long long
using namespace std;
vector<pair<ll, bool> >nodes;
ll distNext[200001]; // Distancia de este nodo con el siguiente de otro color
ll distanciaAcum[200005]; // distancia acumulada si tomo desde i y lo uno con el siguiente del otro color
int siguiente[200005]; // siguiente del otro color
int nm;
ll mem[200005];
ll toPut[200005];
struct segTree{
ll minimo, lazy;
int dd, ht, mid;
segTree *L, *R;
segTree(int l, int r){
dd = l, ht = r;
mid = (dd + ht)/2;
lazy = 0;
minimo = 0;
if(l == r){
minimo = toPut[dd];
}else{
L = new segTree(l, mid);
R = new segTree(mid+1, r);
minimo = min(L->minimo, R->minimo);
}
}
void propagate(){
L->lazy += lazy;
R->lazy += lazy;
if(L->minimo != LLONG_MAX)L->minimo += lazy;
if(R->minimo != LLONG_MAX)R->minimo += lazy;
//L->minimo += lazy;
//R->minimo += lazy;
lazy = 0;
}
void update(int l, int r, ll value){
if(l == dd and r == ht){
lazy += value;
if(minimo != LLONG_MAX)minimo += value;
return ;
}
propagate();
if(r <= mid){
L->update(l, r, value);
}else if(l > mid){
R->update(l, r, value);
}else{
L->update(l, mid, value);
R->update(mid+1, r, value);
}
minimo = min(L->minimo, R->minimo);
}
ll query(int l, int r){
//cout << dd << " " << ht << " " << "query :" << l << " " << r << " " << minimo << endl;
if(dd == l and r == ht)return minimo;
propagate();
if( r <= mid)return L->query(l, r);
else if( mid < l)return R->query(l, r);
else return min(L->query(l, mid), R->query(mid+1, r));
}
};
ll dp(int node){
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
memset(mem, -1, sizeof mem);
int ir = r.size() -1, ib = 0;
ll ans = 0;
nm = r.size() + b.size();
for(auto i : r)nodes.pb({i, 0});
for(auto i : b)nodes.pb({i, 1});
sort(nodes.begin(), nodes.end());
ll last0 = -1, last1 = -1;
int ultimo0 = -1, ultimo1 = -1;
for(int i = nm-1 ; i >= 0 ; i --){
if(nodes[i].color == 0){
//cout << 0 << " ";
if(last1-nodes[i].pos < 0){
distNext[i] = -1;
}else{
distNext[i] = last1-nodes[i].pos;
}
last0 = nodes[i].pos;
ultimo0 = i;
siguiente[i] = ultimo1;
}else{
//cout << 1 << " ";
if(last0-nodes[i].pos < 0){
distNext[i] = -1;
}else{
distNext[i] = last0-nodes[i].pos;
}
last1 = nodes[i].pos;
ultimo1 = i;
siguiente[i] = ultimo0;
}
}
ll distCum[2];
distCum[0] = 0;
distCum[1] = 0;
for(int i = nm-1 ; i >= 0 ; i --){
if(distNext[i] != -1){
distCum[nodes[i].color] += distNext[i];
distanciaAcum[i] = distCum[nodes[i].color];
}else distanciaAcum[i] = -1;
if(nodes[i].color == 0)distCum[1] = 0;
else distCum[0] = 0;
}
bool currentColor = nodes[nm-1].color;
int cuenta = 0, otraCuenta = 0;
int idx = nm-1;
mem[nm] = 0;
for(; idx>= 0 ; idx --){
if(nodes[idx].color != currentColor)break;
cuenta ++;
mem[idx] = LLONG_MAX;
}
for(; idx >= 0 ;){
currentColor = nodes[idx].color;
otraCuenta = 1;
toPut[0] = 0;
ll acum = 0;
for(int i = 1 ; i <= cuenta ; i ++){ // agarrando i
toPut[i] = acum;
//if(mem[idx+i+1] == LLONG_MAX)toPut[i] = ((ll)INT_MAX) * 10000; /// caution
if(min(mem[idx+i+1], mem[idx+i]) == LLONG_MAX)toPut[i] = LLONG_MAX;
else toPut[i] += nodes[idx+i].pos-nodes[idx].pos + min(mem[idx+i+1], mem[idx+i]);
acum += nodes[idx+i].pos-nodes[idx].pos;
//cout << "tt " << i << " " << toPut[i] << endl;
}
segTree *currentState = new segTree(1, cuenta);
//cout << "FROM " << idx << endl;
//for(int i = 1 ; i <= cuenta ; i ++)cout << " taking " << i << ": " << currentState->query(i, i) <<endl;
mem[idx] = currentState->query(1, cuenta);
//cout << "ans for " << idx << " = " << mem[idx] << endl;
idx--;
while(nodes[idx].color == currentColor){
otraCuenta ++ ;
currentState->update(1, min(otraCuenta-1, cuenta), nodes[siguiente[idx]].pos - nodes[idx].pos);
if(min(otraCuenta-1, cuenta) + 1 <= cuenta){
currentState->update(min(otraCuenta-1, cuenta) + 1, cuenta, nodes[siguiente[idx]-1].pos - nodes[idx].pos);
}
//cout << "FROM " << idx << endl;
//for(int i = 1 ; i <= cuenta ; i ++)cout << " taking " << i << ": " << currentState->query(i, i) <<endl;
mem[idx] = currentState->query(1, cuenta);
//cout << "ans for " << idx << " = " << mem[idx] << endl;
idx--;
}
cuenta = otraCuenta;
}
return mem[0];
}
