#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
struct point
{
int pos, id, ty;
point() {}
point(int a, int b, int c)
{
pos=a;
id=b;
ty=c;
}
};
bool cmp(point p, point q)
{
return p.pos<q.pos;
}
int n;
int poss[200005], post[200005];
vector<int> gr[400005];
point p[400005];
int brt=0;
int tree[400005];
void dfs(int v)
{
int brs=gr[v].size();
for(int i=0; i<brs; i++)
{
int nv=gr[v][i];
if(!tree[nv])
{
tree[nv]=brt;
dfs(nv);
}
}
}
int par[400005];
int dp[400005];
vector<pair<int, pair<int, int> > > edges;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
s.push_back(1000000005);
t.push_back(1);
n=s.size();
for(int i=0; i<n; i++)
{
p[2*i]=point(s[i], i, 1);
p[2*i+1]=point(t[i], i, -1);
}
sort(p, p+2*n, cmp);
long long ans=0;
long long sm=0;
for(int i=0; i<2*n; i++)
{
if(p[i].ty==-1) poss[p[i].id]=i;
if(p[i].ty==1) post[p[i].id]=i;
}
for(int i=0; i<n; i++) gr[poss[i]].push_back(post[i]);
for(int i=0; i<2*n; i++)
{
sm+=p[i].ty;
if(i && p[i].pos==p[i-1].pos) {gr[i-1].push_back(i); gr[i].push_back(i-1);}
if(sm>0) {ans+=sm*(p[i+1].pos-p[i].pos); gr[i+1].push_back(i); gr[i].push_back(i+1);}
if(sm<0) {gr[i+1].push_back(i); gr[i].push_back(i+1);}
}
for(int i=0; i<2*n; i++)
{
if(!tree[i])
{
brt++;
tree[i]=brt;
dfs(i);
}
}
///cout<<ans<<endl;
for(int i=1; i<=brt; i++) {par[i]=i; dp[i]=1;}
for(int i=0; i<2*n-1; i++)
{
if(tree[i]==tree[i+1]) continue;
edges.push_back({p[i+1].pos-p[i].pos,{tree[i], tree[i+1]}});
}
sort(edges.begin(), edges.end());
int m=edges.size();
for(int i=0; i<m; i++)
{
int v1=edges[i].second.first, v2=edges[i].second.second;
while(v1!=par[v1]) v1=par[v1];
while(v2!=par[v2]) v2=par[v2];
if(v1==v2) continue;
ans+=edges[i].first;
if(dp[v1]>dp[v2]) par[v2]=v1;
else if(dp[v1]<dp[v2]) par[v1]=v2;
else
{
par[v1]=v2;
dp[v2]++;
}
}
return ans;
}
