#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "railroad.h"
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int H = 2e5 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);
//ifstream in(".in");
//ofstream out(".out");
int n, m, p[H], siz[H];
ll pref[H];
struct edge{
int ff, ss, w;
};
int find_set(int x){
if(x == p[x])return x;
return p[x] = find_set(p[x]);
}
void unionn(int x, int y){
x = find_set(x);
y = find_set(y);
if(x == y)return;
if(siz[x] < siz[y])swap(x, y);
p[y] = x;
siz[x] += siz[y];
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
n = sz(s);
ll ans = 0;
vector<int>v;
for(int i = 0; i < n; i++){
v.push_back(s[i]);
v.push_back(t[i]);
}
sort(all(v));
v.resize(unique(all(v))-v.begin());
m = sz(v);
for(int i = 0; i < m; i++){
p[i] = i;
pref[i] = 0;
siz[i] = 1;
}
pref[1] = -1;
for(int i = 0; i < n; i++){
s[i] = lower_bound(all(v), s[i]) - v.begin();
t[i] = lower_bound(all(v), t[i]) - v.begin();
pref[s[i]]++;
pref[t[i]]--;
unionn(s[i], t[i]);
}
vector<edge>edges;
for(int i = 0; i < m - 1; i++){
pref[i] += (i == 0 ? 0 : pref[i - 1]);
if(pref[i] != 0){
ans += max(0ll, pref[i])*(v[i + 1] - v[i]);
unionn(i, i + 1);
}
edges.push_back({i, i + 1, v[i + 1] - v[i]});
}
for(auto it : edges){
if(find_set(it.ff) == find_set(it.ss))continue;
ans += it.w;
unionn(it.ff, it.ss);
}
return ans;
}
