#include "railroad.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define sz(s) (int)s.size()
#define in insert
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define lb lower_bound
using namespace std;
const int MAX=2e5+10;
const ll inf=1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<int> g[MAX*10];
int bal[10*MAX];
struct DSU{
int f[MAX];
void init(int n){
for(int i=0;i<=n;i++)f[i]=i;
}
int get(int v){
return (f[v]==v?v:f[v]=get(f[v]));
}
void unite(int u,int v){
u=get(u);
v=get(v);
if(rng()%2)swap(u,v);
f[u]=v;
}
}D;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
vector<int> vec;
n=sz(s);
for(int i=0;i<n;i++)vec.pb(s[i]);
for(int i=0;i<n;i++)vec.pb(t[i]);
sort(all(vec));
vec.erase(unique(all(vec)),vec.end());
for(int i=0;i<n;i++){
s[i]=lb(all(vec),s[i])-vec.begin();
t[i]=lb(all(vec),t[i])-vec.begin();
}
D.init(sz(vec));
for(int i=0;i<n;i++){
D.unite(s[i],t[i]);
}
int ans=0;
for(int i=0;i<n;i++){
if(s[i]<t[i]){
bal[s[i]]++;
bal[t[i]]--;
}
else{
bal[t[i]]--;
bal[s[i]]++;
}
}
for(int i=1;i<sz(vec);i++){
bal[i]+=bal[i-1];
}
D.unite(0,sz(vec));
for(int i=0;i<sz(vec);i++){
bal[i]--;
}
vector<pair<int,pii>> edges;
for(int i=0;i<sz(vec);i++){
if(bal[i]==0){
edges.pb({vec[i+1]-vec[i],{i,i+1}});
}
else{
if(bal[i]>0)ans+=bal[i]*(vec[i+1]-vec[i]);
D.unite(i,i+1);
}
}
sort(all(edges));
for(auto [a,b]:edges){
if(D.get(b.F)!=D.get(b.S)){
D.unite(b.F,b.S);
ans+=a;
}
}
return ans;
}
