#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
struct Edge{
int x, y; ll z;
Edge(){}
Edge(int x, int y, ll z): x(x), y(y), z(z){}
bool operator<(const Edge &r)const{
return z > r.z;
}
};
int n, k;
vector<int> vec;
map<int, int> idx;
vector<int> link[500002];
vector<int> revLink[500002];
ll ans;
int par[500002];
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[x] = y;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
n = (int)s.size();
for(int i=0; i<n; i++){
vec.push_back(s[i]);
vec.push_back(t[i]);
}
vec.push_back(1);
vec.push_back(1e9);
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
k = (int)vec.size();
for(int i=0; i<k; i++) idx[vec[i]] = i;
for(int i=0; i<n; i++){
s[i] = idx[s[i]];
t[i] = idx[t[i]];
link[s[i]].push_back(t[i]);
revLink[t[i]].push_back(s[i]);
}
link[k-1].push_back(0);
revLink[0].push_back(k-1);
int need = 0;
for(int i=0; i<k; i++){
need += (int)link[i].size();
need -= (int)revLink[i].size();
if(need < 0){
link[i].push_back(i+1);
revLink[i+1].push_back(i);
need++;
}
else if(need > 0){
link[i+1].push_back(i);
revLink[i].push_back(i+1);
ans += ll(vec[i+1] - vec[i]) * need;
need--;
}
}
for(int i=0; i<k; i++) par[i] = i;
for(int i=0; i<k; i++){
for(auto x: link[i]){
merge(i, x);
}
}
priority_queue<Edge> pq;
for(int i=0; i<k-1; i++){
pq.push(Edge(i, i+1, vec[i+1] - vec[i]));
}
while(!pq.empty()){
Edge tmp = pq.top(); pq.pop();
if(find(tmp.x) == find(tmp.y)) continue;
ans += tmp.z;
merge(tmp.x, tmp.y);
}
return ans;
}
