#include "railroad.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
struct mode
{
ll p,v,i;
bool operator<(const mode&x)const{
return p<x.p;
}
};
struct edge
{
ll a,b,w;
bool operator<(const edge&x)const{
return w<x.w;
}
};
ll boss[200005];
ll finds(ll a)
{
if(a==boss[a]) return a;
return boss[a]=finds(boss[a]);
}
void Union(ll a,ll b)
{
a=finds(a),b=finds(b);
if(a==b) return;
boss[a]=b;
}
ll plan_roller_coaster(vector<int> s,vector<int> t)
{
ll n=s.size()+1,ans=0,nw=0;
vector<mode> v;
vector<pii> interesting;
vector<edge> e;
s.pb(1000000001),t.pb(1);
for(int i=0;i<n;++i)
boss[i]=i,v.pb(mode{s[i],1,i}),v.pb(mode{t[i],-1,i});
sort(ALL(v));
for(int i=0,t=0;i+1<v.size();)
{
interesting.pb(MP(v[i].p,v[i].i));
while(t<v.size()&&v[i].p==v[t].p)
nw+=v[t].v,++t;
if(nw>0)
ans+=nw*(v[t].p-v[i].p);
if(nw!=0)
Union(v[t].i,v[i].i);
for(++i;i<t;++i)
Union(v[i-1].i,v[i].i);
}
for(int i=0;i+1<interesting.size();++i)
if(finds(interesting[i].S)!=finds(interesting[i+1].S))
e.pb(edge{interesting[i].S,interesting[i+1].S,interesting[i+1].F-interesting[i].F});
sort(ALL(e));
for(auto i:e)
if(finds(i.a)!=finds(i.b))
Union(i.a,i.b),ans+=i.w;
return ans;
}
