#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx = 2e5 + 5;
const int maxNode = nx * 2;
int n, m;
int pa[maxNode];
int ct[maxNode];
int fp(int n) {
if (pa[n] == n) return n;
return pa[n] = fp(pa[n]);
}
void unite(int u, int v) {
int pu = fp(u), pv = fp(v);
if (pu == pv) return;
pa[pu] = pv;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
n = (int) s.size();
for (int i = 1; i < maxNode; i++) pa[i] = i;
vector<ll> v;
for (int i = 0; i < n; i++) {
v.emplace_back(s[i]);
v.emplace_back(t[i]);
}
v.emplace_back(1);
v.emplace_back(1e9 + 5);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
m = v.size();
for (int i = 0; i < n; i++) {
//cout << s[i] << " " << t[i] << " : ";
s[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin() + 1;
t[i] = lower_bound(v.begin(), v.end(), t[i]) - v.begin() + 1;
unite(s[i], t[i]);
ct[s[i]]++;
ct[t[i]]--;
//cout << s[i] << " "<< t[i] << endl;
}
ct[1]--;
ct[m]++;
unite(1, m);
ll sum = 0;
ll ans = 0;
for (int i = 1; i + 1 <= m; i++) {
sum += ct[i];
ll dist = v[i] - v[i - 1];
//cout << v[i - 1] << " " << v[i] << " " << dist << " " << ct[i] << endl;
if (sum > 0) {
ans += dist;
unite(i, i + 1);
} else if (sum < 0) unite(i, i + 1);
}
priority_queue<tuple<ll,int,int>,vector<tuple<ll,int,int>>,greater<tuple<ll,int,int>>> pq;
for (int i = 1; i + 1 <= m; i++) {
ll dist = v[i] - v[i - 1];
pq.emplace(dist, i, i + 1);
}
while (!pq.empty()) {
auto [w, u, v] = pq.top();
pq.pop();
if (fp(u) == fp(v)) continue;
pa[fp(u)] = fp(v);
ans += w;
}
return ans;
}
/*
4
1 7
4 3
5 8
6 6
3
*/
