#include "wiring.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = 1000002022;
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
#define P pair
struct segtree {
private:
struct node {
ll val;
};
node single(ll v) {
return {v};
}
node neutral={(ll)1e17};
node merge(node a,node b) {
return{min(a.val,b.val)};
}
public:
int size;
V<node>query;
void init(int n) {
size=1;
while (size<n)size*=2;
query.assign(2*size,neutral);
}
void set(ll i,ll v,ll x,ll lx,ll rx) {
if (rx-lx==1) {
query [x]=single(v);
return;
}
ll m=(lx+rx)/2;
if (i<m)
set(i,v,2*x+1,lx,m);
else
set(i,v,2*x+2,m,rx);
query[x]=merge(query[2*x+1],query[2*x+2]);
}
void set(ll i,ll v) {
set(i,v,0,0,size);
}
node calc(ll l,ll r,ll x,ll lx,ll rx) {
if (lx>=r || rx<=l) {
return neutral;
}
if (l<=lx && rx<=r) {
return query[x];
}
ll m=(lx+rx)/2;
node a=calc(l,r,2*x+1,lx,m);
node b=calc(l,r,2*x+2,m,rx);
return merge(a,b);
}
ll calc(ll l,ll r) {
return calc(l,r,0,0,size).val;
}
};
ll x[(int)1e6+1],y[(int)1e6+1],pref[(int)1e6+1];
int p[(int)1e6+1];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
V<P<int,int>>vp;
vp.pb({0,0});
for (auto u:r) {
vp.pb({u,0});
}
for (auto u:b) {
vp.pb({u,1});
}
sort(all(vp));
int n=(int)r.size()+(int)b.size();
V<ll>a(n+1);V<int>t(n+1);
for (int i=1;i<=n;i++) {
a[i]=vp[i].F;
t[i]=vp[i].S;
}
p[0]=-1;
pref[0]=0;
for (int i=1;i<=n;i++) {
pref[i]=pref[i-1]+a[i];
}
int curr=-1,id=-1;
for (int i=n;i>=1;i--) {
if (t[i]!=curr) {
curr=t[i];
id=i;
}
x[i]=a[id];
if (id+1<=n) {
y[i]=a[id+1];
}
}
curr=-1,id=-1;
for (int i=1;i<=n;i++) {
if (t[i]!=curr) {
curr=t[i];
id=i;
}
p[i]=id;
}
V<ll>dp(n+1,1e17);
dp[0]=0LL;
segtree tree1,tree2;
tree1.init(n+1);
tree2.init(n+1);
for (ll i=1;i<=n;i++) {
if (p[i]>1) {
ll len=i-p[i]+1;
ll l=p[p[i]-1]-1;
ll lb=max(l,p[i]-len-1);
ll c=1e17,c1=1e17;
if(lb<p[i]-1) {
c=pref[i]-2LL*pref[p[i]-1]-(len-p[i]+1)*a[p[i]-1]+tree1.calc(lb,p[i]-1);
}
if (l<lb) {
c1=pref[i]-2LL*pref[p[i]-1]+(p[i]-1-len)*a[p[i]]+tree2.calc(l,lb);
}
dp[i]=min(c1,c);
}
tree1.set(i-1,min(dp[i],dp[i-1])+pref[i-1]-(i-1)*x[i]);
tree2.set(i-1,min(dp[i],dp[i-1])+pref[i-1]-(i-1)*y[i]);
}
return dp[n];
}
