#include "wiring.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10;
const long long inf = 1e18;
int a[N] , col[N] , n , prv[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 las1 = 1 , las2 = 1 , cnt1 = 0 , cnt2 = 0;
for(int i = id ; i > 0 ; i--)
{
if(col[i] != col[id])
{
las1 = i + 1;
break;
}
cnt1++;
}
for(int i = las1 - 1 ; i > 0 ; i--)
{
if(col[i] != col[las1 - 1])
{
las2 = i + 1;
break;
}
cnt2++;
}
if(cnt2 == 0)
{
dp[id] = inf;
return;
}
if(cnt1 >= cnt2)
{
dp[id] = min(dp[las2 - 1] , dp[las2]);
for(int i = id ; i >= las2 ; i--)
dp[id] += (col[i] == col[id] ? a[i] : -a[i]);
dp[id] -= 1LL * (cnt1 - cnt2) * a[las1 - 1];
return;
}
for(int i = 0 ; i < cnt1 ; i++)
{
dp[id] += (a[id - i] - a[las1 - 1 - i]);
}
long long val = inf , sum = 0;
for(int i = las1 - cnt1 - 1 ; i >= las2 ; i--)
{
val = min(val , sum + dp[i]);
sum += (a[las1] - a[i]);
}
val = min(val , sum + dp[las2 - 1]);
dp[id] += val;
return;
}
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;
}
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);
}
return Get(1 , n);
}
