#include "wiring.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 2e5 + 10;
const long long inf = 1e18;
int a[N] , col[N] , n , prv[N] , opt[N];
long long dp[N] , psum[N];
long long Sum(int l , int r)
{
return psum[r] - psum[l - 1];
}
long long Get(int l , int r)
{
int mid = prv[r];
if(mid <= l)
return inf;
int c1 = r - mid + 1 , c2 = mid - l;
long long res = Sum(mid , r) - Sum(l , mid - 1);
if(c1 >= c2)
res -= 1LL * (c1 - c2) * a[mid - 1];
else
res += 1LL * (c2 - c1) * a[mid];
return res;
}
void Solve(int id)
{
int las = prv[id];
if(las == 1)
{
dp[id] = inf;
return;
}
int las2 = prv[las - 1];
if(las2 == 1)
{
dp[id] = Get(1 , id);
return;
}
if(las == id)
opt[id] = las - 1;
else
opt[id] = opt[id - 1];
dp[id] = Get(opt[id] , id) + min(dp[opt[id] - 1] , dp[opt[id]]);
while(opt[id] != las2 && Get(opt[id] - 1 , id) + min(dp[opt[id] - 2] , dp[opt[id] - 1]) < dp[id])
{
dp[id] = Get(opt[id] - 1 , id) + min(dp[opt[id] - 2] , dp[opt[id] - 1]);
opt[id]--;
}
}
long long min_total_length(vector<int> r, vector<int> b) {
n = r.size() + b.size();
vector <pair<int , int>> vec;
for(auto u : r)
vec.push_back({u , 0});
for(auto u : b)
vec.push_back({u , 1});
sort(vec.begin() , vec.end());
for(int i = 1 ; i <= n ; i++)
{
a[i] = vec[i - 1].F;
col[i] = vec[i - 1].S;
}
dp[0] = 0;
prv[1] = 1;
psum[1] = a[1];
for(int i = 2 ; i <= n ; i++)
{
psum[i] = psum[i - 1] + a[i];
prv[i] = (col[i] == col[i - 1] ? prv[i - 1] : i);
}
for(int i = 1 ; i <= n ; i++)
Solve(i);
return dp[n];
}
