#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
struct medis {
const long long inf = 1e18;
vector<long long> val;
int n;
medis (int dd) {
n = dd;
val.resize(4*n);
for(auto &x : val) x = inf;
}
void change(int v, int nL, int nR, int L, int R, long long x) {
int mid = (nL + nR) / 2;
if(L <= nL && nR <= R) {
val[v] = x;
}else if(L > nR || nL > R) {
return ;
}else {
change(v*2, nL, mid, L, R, x);
change(v*2+1, mid+1, nR, L, R, x);
val[v] = min(val[v*2], val[v*2+1]);
}
}
long long getMin(int v, int nL, int nR, int L, int R) {
int mid = (nL + nR) / 2;
if(L <= nL && nR <= R) {
return val[v];
}else if(L > nR || nL > R) {
return inf;
}else {
return min(getMin(v*2, nL, mid, L, R), getMin(v*2+1, mid+1, nR, L, R));
}
}
};
int n;
const long long inf = 1e18;
vector<int> groupInd;
vector<pair<int, int> > interv;
vector<pair<int, int> > groups;
vector<long long> toRight, toLeft;
vector<long long> ikiL, ikiR;
vector<long long> kaimL, kaimR;
const int dydis = 2e5 + 10;
medis asMax(dydis), jisMax(dydis);
long long f(int l, int r) {
long long ret = 0;
ret += toRight[l];
ret += toLeft[r];
ret += kaimR[l] * max(ikiR[l], ikiL[r]);
return ret;
}
void calcToLeft(int l, int r, int ind) {
int dst = -1;
if(ind != 0) dst = abs(groups[interv[ind-1].second].first - groups[l].first);
for(int i = l; i <= r; i++) {
toLeft[i] = (i == l ? 0ll : toLeft[i-1]) + groups[i].first - groups[l].first;
ikiL[i] = i - l + 1;
kaimL[i] = dst;
}
}
void calcToRight(int l, int r, int ind) {
int dst = -1;
if(ind != (int) interv.size() - 1) dst = abs(groups[interv[ind+1].first].first - groups[r].first);
for(int i = r; i >= l; i--) {
toRight[i] = (i == r ? 0ll : toRight[i+1]) + groups[r].first - groups[i].first;
ikiR[i] = r - i + 1;
kaimR[i] = dst;
}
}
long long min_total_length(vector<int> r, vector<int> b) {
n = r.size() + b.size();
for(auto &x : r) {
groups.push_back({x, 0});
}
for(auto &x : b) {
groups.push_back({x, 1});
}
groupInd.resize(n);
toLeft.resize(n);
toRight.resize(n);
ikiL.resize(n);
ikiR.resize(n);
kaimL.resize(n);
kaimR.resize(n);
sort(groups.begin(), groups.end());
for(int i = 0; i < n; i++) {
for(int j = i; j <= n; j++) {
if(j == n || groups[j].second != groups[i].second) {
int l = i;
int r = j-1;
interv.push_back({l, r});
for(int h = l; h <= r; h++) {
groupInd[h] = (int) interv.size()-1;
}
i = j-1;
break;
}
}
}
for(int i = 0; i < interv.size(); i++) {
int l = interv[i].first;
int r = interv[i].second;
calcToLeft(l, r, i);
calcToRight(l, r, i);
}
vector<long long> dp(n, inf);
asMax.change(1, 0, dydis-1, 0, 0, toRight[0] + kaimR[0] * ikiR[0]);
jisMax.change(1, 0, dydis-1, 0, 0, toRight[0]);
for(int i = interv[1].first; i < n; i++) {
int myInterv = groupInd[i];
dp[i] = dp[interv[myInterv-1].second] + f(interv[myInterv-1].second, i);
int ikiManoL = ikiL[i];
int marker = max(interv[myInterv-1].second - ikiManoL + 1, interv[myInterv-1].first);
int L = interv[myInterv-1].first;
int R = interv[myInterv-1].second;
dp[i] = min(dp[i], jisMax.getMin(1, 0, dydis-1, marker, R) + kaimL[i] * ikiL[i] + toLeft[i]);
dp[i] = min(dp[i], asMax.getMin(1, 0, dydis-1, L, marker-1) + toLeft[i]);
asMax.change(1, 0, dydis-1, i, i, (i == 0 ? 0ll : dp[i-1]) + toRight[i] + kaimR[i] * ikiR[i]);
jisMax.change(1, 0, dydis-1, i, i, (i == 0 ? 0ll : dp[i-1]) + toRight[i]);
}
return dp[n-1];
}
