#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1e6+99,inf=1e9+99;
int n,m,cnt,f[N],in[N],out[N],vis[N];
ll ans;
vector<int> ga[N],gb[N];
int getpar(int u){
if(f[u]<0) return u;
return f[u]=getpar(f[u]);
}
void merge(int u,int v,int w=0){
u=getpar(u),v=getpar(v);
if(u==v) return ;
if(f[u]>f[v]) swap(u,v);
f[u]+=f[v];
f[v]=u;
ans+=w;
}
void add(int u,int v,int t){
in[v]+=t;
out[u]+=t;
}
ll plan_roller_coaster(vector<int> s,vector<int> t) {
vector<pair<int,pair<int,int>>> edge;
vector<int> vec;
fill(f,f+N,-1);
f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
sort(all(vec));
vec.resize(unique(all(vec))-vec.begin());
n=vec.size();
f(i,0,s.size()){
int u=lower_bound(all(vec),s[i])-vec.begin(),v=lower_bound(all(vec),t[i])-vec.begin();
merge(u,v);
add(u,v,1);
}
merge(0,n-1);
add(n-1,0,1);
f(i,0,n-1){
if(in[i]==out[i]){
edge.pb({vec[i+1]-vec[i],{i,i+1}});
continue ;
}
merge(i,i+1);
if(in[i]<out[i]){
ans+=(out[i]-in[i])*(vec[i+1]-vec[i]);
}
if(in[i]>out[i]){
add(i,i+1,in[i]-out[i]);
}
}
sort(all(edge));
for(auto [w,e] : edge){
merge(e.F,e.S,w);
}
return ans;
}
