#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(ll a=ll(b); a<ll(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(ll a=ll(c-1); a>=ll(b); a--)
#define INF 1e18
#define pb push_back
#define fi first
#define se second
#define sz size()
// min segment tree library
template <class T=int, T MAX=1000000000, T DEF=0>
class MinSegmentTree {
public:
void resize(int _size) {
size = _size;
SEG.assign(size*4, DEF);
LAZ.assign(size*4, 0);
}
void add(int i, int j, T x, T lazy, int p, int l, int r) {
SEG[p] += lazy;
LAZ[p] += lazy;
if(j < l || i > r) return;
if(i <= l && j >= r) {
SEG[p] += x;
LAZ[p] += x;
return;
}
int m=(l+r)/2;
add(i,j,x,LAZ[p],p*2+1,l,m);
add(i,j,x,LAZ[p],p*2+2,m+1,r);
SEG[p] = min(SEG[p*2+1], SEG[p*2+2]);
LAZ[p] = 0;
}
void set(int i, T x, T lazy, int p, int l, int r) {
SEG[p] += lazy;
LAZ[p] += lazy;
if(i < l || i > r) return;
if(l == r) {
SEG[p] = x;
return;
}
int m=(l+r)/2;
set(i,x,LAZ[p],p*2+1,l,m);
set(i,x,LAZ[p],p*2+2,m+1,r);
SEG[p] = min(SEG[p*2+1], SEG[p*2+2]);
LAZ[p] = 0;
}
T getMin(int i, int j, T lazy, int p, int l, int r) {
if(j < i) return MAX;
SEG[p] += lazy;
LAZ[p] += lazy;
if(j < l || i > r) return MAX;
if(i <= l && j >= r) return SEG[p];
int m=(l+r)/2;
T a=getMin(i,j,LAZ[p],p*2+1,l,m);
T b=getMin(i,j,LAZ[p],p*2+2,m+1,r);
return min(a,b);
}
inline void add(int i, int j, T x) {add(i,j,x,0,0,0,size-1);}
inline void add(int i, T x) {add(i,i,x,0,0,0,size-1);}
inline void set(int i, T x) {set(i ,x,0,0,0,size-1);}
inline T getMin(int i, int j) {return getMin(i,j,0,0,0,size-1);}
inline T getMin(int i) {return getMin(i,i,0,0,0,size-1);}
vector<T> SEG, LAZ;
int size;
};
typedef MinSegmentTree<int,1000000000,0> MinSegI;
typedef MinSegmentTree<long long,1000000000000000000,0> MinSegLL;
//===================//
// begin program //
//===================//
const ll MX = 5e5;
vi pos, col;
bitset<MX> connected;
ll n, m, N;
ll nxtC[MX];
ll dp[MX];
ll gd(ll i, ll j) {
return abs(pos[i] - pos[j]);
}
MinSegLL seg1, seg2;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
n = r.sz, m = b.sz;
N = n+m;
{
ll i=0, j=0;
while(i != n || j != m) {
if(j == m || (i != n && r[i] < b[j])) {
pos.pb(r[i++]);
col.pb(0);
} else {
pos.pb(b[j++]);
col.pb(1);
}
}
}
dp[0] = 0;
ll beg = -1, cent=-1, lastCol=-1;
seg1.resize(N+1);
seg2.resize(N+1);
ll totCost = 0;
REP(i,1,N+1) {
if(col[i-1] != lastCol) {
lastCol = col[i-1];
beg = cent;
cent = i-1;
REI(x,beg,cent) seg1.set(x,dp[x]);
REI(x,beg,cent-1) seg1.add(beg,x,-pos[x]);
REI(x,beg,cent) seg1.add(x,x,-pos[cent - 1]*x);
REI(x,beg,cent) seg2.set(x,dp[x]);
REI(x,beg,cent-1) seg2.add(beg,x,-pos[x]);
REI(x,beg,cent) seg2.add(x,x,-pos[cent]*x);
totCost = 0;
}
totCost += pos[i-1];
dp[i] = INF;
if(beg == -1) continue;
ll y = i-1;
dp[i] = min(dp[i], seg1.getMin(max(beg,2*cent-y), cent)+pos[cent - 1] * (2*cent - y - 1)+totCost);
dp[i] = min(dp[i], seg2.getMin(beg,min(cent,2*cent-y-1))+pos[cent] * (2*cent - y - 1)+totCost);
}
return dp[N];
}
