#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int N=4e5+5;
const int INF=1e9;
int n,bal[N],p[N]; ll res=0;
vi rar;
int find(int x){
return p[x]==x ? x : p[x]=find(p[x]);
}
bool unite(int x, int y){
x=find(x); y=find(y);
if(x!=y){
p[y]=x;
return true;
}
return false;
}
ll plan_roller_coaster(vi s, vi t) {
s.eb(INF), t.eb(1);
n=sz(s);
rep(i,n) rar.eb(s[i]), rar.eb(t[i]);
sort(all(rar));
rar.erase(unique(all(rar)),rar.end());
rep(i,n){
s[i]=lower_bound(all(rar),s[i])-rar.begin();
t[i]=lower_bound(all(rar),t[i])-rar.begin();
}
iota(p,p+sz(rar),0);
rep(i,n){
bal[s[i]]++; bal[t[i]]--;
unite(s[i],t[i]);
}
rep(i,sz(rar)){
if(i>0) bal[i]+=bal[i-1];
if(bal[i]!=0){ /// must have edge which go through this (greedy here to connect these)
unite(i,i+1);
res+=max(0LL,1LL*(rar[i+1]-rar[i])*bal[i]);
}
}
vector<pair<int,ii>> eds;
rep(i,sz(rar)-1){
if(find(i)!=find(i+1)){
eds.pb({rar[i+1]-rar[i],{i,i+1}});
}
}
sort(all(eds));
for(pair<int,ii> e:eds){
if(unite(e.se.fi,e.se.se)){
res+=e.fi;
}
}
return res;
}
