#define _CRT_SECURE_NO_WARNINGS
#include "wiring.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define sz(l,r) (r-l+1)
#define sum(l,r) ((long long)((int)r>=(int)l ? (long long)(pre[r]-(l==0 ? 0ll:pre[l-1])):0ll) -sz(l,r)*val[l])
const int N = 2e5 + 7;
struct seg {
int tl, tr;
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<pair<int, int>> all;
for (int to : r)all.push_back({ to,0 });
for (int to : b)all.push_back({ to,1 });
int n = all.size();
sort(all.begin(), all.end());
vector<int> kind, val,left(n,0);
for (int i = 0; i < n; ++i) {
kind.push_back(all[i].second);
val.push_back(all[i].first);
if (i == 0 || kind[i] != kind[i - 1]) {
left[i] = i;
}
else left[i] = left[i - 1];
}
vector<long long> dp(n, (long long)1e18),pre(n,0),dpmx(n,(long long)1e18);
for (int i = 0; i < n; ++i)if (i == 0)pre[i] = val[i]; else pre[i] = val[i] + pre[i - 1];
int opt=-1;
for (int i = 0; i < n; ++i) {
// cout << "current i = "<<i<<" opt= "<<opt<<":\n"<< endl;
if (left[i] == 0) {
dp[i] = 0; continue;
}
auto gum=[&] (int l, int r) {
int m = left[r];
// cout << "left=="<<l<<" and Left of "<<r<<" is "<<m <<":\n"<< endl;
// cout << "sum(" << l << "," << m - 1 << ") = " << sum(l, m - 1) << endl;
// cout << "sum(" << m << "," << r << ") = " << sum(m,r) << endl;
return sum(l, m - 1) + sum(m, r) + max(sz(l, m - 1), sz(m, r))*(val[m]-val[m-1]);
};
if (left[left[i] - 1] == 0) {
dp[i] = gum(left[left[i]-1],i);
}
else if (i == left[i]) {
opt = left[left[i] - 1] + (left[left[i-1]-1]==0);
for (; opt < left[i] - 1; ++opt) {
if (gum(opt, i) + dpmx[opt - 1] >= gum(opt + 1, i) + dpmx[opt]) {
continue;
}
break;
}
dp[i] = gum(opt, i) + dpmx[opt - 1];
}
else {
int L = left[left[i] - 1];
if (opt == L) {
dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
}
else {
if (left[i] - 1 - opt > i - left[i]-1) {
dp[i] = dp[i - 1] + val[i] - val[i - 1];
}
else {
if (left[i] - opt - 1 == i - left[i]-1) {
if (opt-1>=L&&dpmx[opt - 2] + gum(opt-1, i) <= dpmx[opt-1]+gum(opt,i)) {
dp[i] = dpmx[opt - 2] + gum(opt - 1, i);
opt--;
}
else {
dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
}
}
else {
dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
}
}
}
}
if (i != n - 1 && left[i + 1] != left[i]) {
for (int r = i; r >= left[i]; r--) {
if (r == i)dpmx[r] = dp[r];
else dpmx[r] = min(dp[r], dpmx[r + 1]);
}
}
}
return dp[n-1];
}
