#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
long long balance[400005]; int p[400005];
vector<pair<int, pair<int,int> > > edges;
int findSet(int u){
if(u == p[u]) return u;
else return p[u] = findSet(p[u]);
}
bool unionSet(int u, int v){
int x = findSet(u);
int y = findSet(v);
if(x == y) return false;
p[x] = y;
return true;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
s.push_back(2e9); t.push_back(1);
int n = (int) s.size();
vector<long long> points;
for(int i = 0;i < n;i++) points.push_back(s[i]), points.push_back(t[i]);
sort(points.begin(),points.end());
points.erase(unique(points.begin(),points.end()), points.end());
for(int i = 0;i < (int) points.size();i++) p[i] = i;
for(int i = 0;i < n;i++){
s[i] = lower_bound(points.begin(),points.end(),s[i]) - points.begin();
t[i] = lower_bound(points.begin(),points.end(),t[i]) - points.begin();
balance[s[i]]++;
balance[t[i]]--;
unionSet(s[i],t[i]);
}
long long ans = 0, acc = 0;
for(int i = 0;i < (int) points.size() - 1;i++){
acc += balance[i];
if(acc == 0) edges.push_back({points[i+1] - points[i], {i, i+1}});
else{
unionSet(i,i+1);
if(acc > 0) ans += (points[i+1] - points[i]) * acc;
}
}
sort(edges.begin(),edges.end());
for(auto& e : edges){
if(unionSet(e.second.first,e.second.second)){
ans += e.first;
}
}
return ans;
}
