/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long ll;
const int N_MAX = 200002;
const ll INF = LLONG_MAX / 2;
struct Node
{
ll x;
bool color;
};
bool operator < (const Node &a, const Node &b)
{
return a.x < b.x;
}
int n;
Node v[N_MAX];
int prevL[N_MAX], prevR[N_MAX];
int L[N_MAX], R[N_MAX];
ll sumPref[N_MAX];
ll dp[N_MAX];
ll SGT1[N_MAX * 4], SGT2[N_MAX * 4];
void build (ll SGT[], int node, int l, int r)
{
if(l == r)
{
SGT[node] = INF;
return;
}
int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
build(SGT, lSon, l, mid);
build(SGT, rSon, mid + 1, r);
SGT[node] = min(SGT[lSon], SGT[rSon]);
}
void update (ll SGT[], int node, int l, int r, int upos, ll uval)
{
if(l == r)
{
SGT[node] = uval;
return;
}
int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
if(upos <= mid)
update(SGT, lSon, l, mid, upos, uval);
else
update(SGT, rSon, mid + 1, r, upos, uval);
SGT[node] = min(SGT[lSon], SGT[rSon]);
}
ll query (ll SGT[], int node, int l, int r, int ql, int qr)
{
if(ql > qr)
return INF;
if(ql <= l && r <= qr)
return SGT[node];
int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
if(ql <= mid && mid + 1 <= qr)
return min(query(SGT, lSon, l, mid, ql, qr), query(SGT, rSon, mid + 1, r, ql, qr));
else if(ql <= mid)
return query(SGT, lSon, l, mid, ql, qr);
else
return query(SGT, rSon, mid + 1, r, ql, qr);
}
ll min_total_length (vector <int> rv, vector <int> bv)
{
for(int x : rv)
v[++n] = Node{x, 0};
for(int x : bv)
v[++n] = Node{x, 1};
sort(v + 1, v + n + 1);
int currL = 1, currR = 0;
v[n + 1].color = !v[n].color;
for(int i = 1; i <= n + 1; i++)
{
if(i > 1 && v[i].color != v[i - 1].color)
{
for(int j = i - 1; j >= 1 && v[j].color == v[i - 1].color; j--)
{
L[j] = currL;
R[j] = currR;
}
prevL[i] = currL;
prevR[i] = currR;
currL = i;
}
else
{
prevL[i] = prevL[i - 1];
prevR[i] = prevR[i - 1];
}
currR = i;
}
for(int i = 1; i <= n; i++)
sumPref[i] = sumPref[i - 1] + v[i].x;
build(SGT1, 1, 1, n);
build(SGT2, 1, 1, n);
update(SGT1, 1, 1, n, 1, - v[R[1] + 1].x);
update(SGT2, 1, 1, n, 1, - v[R[1]].x);
for(int i = 1; i <= n; i++)
{
if(prevL[i] == 0)
dp[i] = INF;
else
{
int k = prevR[i];
int l1 = prevL[i], r1 = min(prevR[i], 2 * k - i);
int l2 = max(prevL[i], 2 * k - i + 1), r2 = prevR[i];
dp[i] = min({INF,
query(SGT1, 1, 1, n, l1, r1) + sumPref[i] - 2 * sumPref[k] + v[k + 1].x * (2 * k - i + 1),
query(SGT2, 1, 1, n, l2, r2) + sumPref[i] - 2 * sumPref[k] - v[k].x * (i - 2 * k - 1)});
update(SGT1, 1, 1, n, i, min(dp[i], dp[i - 1]) + sumPref[i - 1] - v[R[i] + 1].x * i);
update(SGT2, 1, 1, n, i, min(dp[i], dp[i - 1]) + sumPref[i - 1] - v[R[i]].x * i);
}
}
return dp[n];
}
