#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long ma=1e9;
long long n,dsu[400069];
pair<long long,pair<long long,long long>> as[400069],ed[400069];
pair<long long,long long> pst[200069];
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
long long plan_roller_coaster(vector<int> ka,vector<int> la)
{
long long i,k,l,w,c=0,z=0;
n=ka.size()+1;
for(i=1;i<=n;i++)
{
if(i<n)
{
k=ka[i-1];
l=la[i-1];
}
else
{
k=ma+1;
l=0;
}
z+=l-k;
as[i*2-1]={k,{i,1}};
as[i*2]={l,{i,-1}};
}
sort(as+1,as+n*2+1);
for(i=1;i<=n*2;i++)
{
k=as[i].fr;
l=as[i].sc.fr;
w=as[i].sc.sc;
z+=(k-as[i-1].fr)*abs(c);
dsu[i]=i;
if(c)
{
dsu[fd(i-1)]=fd(i);
}
c+=w;
pst[l].fr=i;
swap(pst[l].fr,pst[l].sc);
}
for(i=1;i<=n;i++)
{
k=pst[i].fr;
l=pst[i].sc;
dsu[fd(l)]=fd(k);
}
for(i=1;i<n*2;i++)
{
ed[i]={(as[i+1].fr-as[i].fr)*2,{fd(i),fd(i+1)}};
}
sort(ed+1,ed+n*2);
for(i=1;i<n*2;i++)
{
w=ed[i].fr;
k=ed[i].sc.fr;
l=ed[i].sc.sc;
z+=w*(fd(k)!=fd(l));
dsu[fd(l)]=fd(k);
}
z/=2;
return z;
}
