#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
const int MAXN = 400005;
int p[MAXN], sz[MAXN], diff[MAXN];
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u, sz[u] += sz[v];
return true;
}
int plan_roller_coaster(std::vector<i32> s, std::vector<i32> t) {
int n = (int) s.size();
vector<int> disc;
for (int i = 0; i < n; i++) {
disc.push_back(s[i]);
disc.push_back(t[i]);
}
sort(disc.begin(), disc.end());
disc.erase(unique(disc.begin(), disc.end()), disc.end());
for (int i = 1; i <= (int) disc.size() + 1; i++) p[i] = i, sz[i] = 1;
for (int i = 0; i < n; i++) {
// cout << s[i] << " " << t[i] << '\n';
s[i] = lower_bound(disc.begin(), disc.end(), s[i]) - disc.begin() + 1;
t[i] = lower_bound(disc.begin(), disc.end(), t[i]) - disc.begin() + 1;
merge(s[i], t[i]);
// cout << "merge: " << s[i] << " " << t[i] << '\n';
diff[s[i]]++, diff[t[i]]--;
}
int sz = disc.size();
merge(sz + 1, 1);
disc.push_back(1e9 + 1);
diff[sz + 1]++, diff[1]--;
for (int i = 1; i <= sz; i++) diff[i + 1] += diff[i];
int ans = 0;
for (int i = 1; i <= sz; i++) {
if (diff[i] != 0) merge(i, i + 1);
if (diff[i] > 0) ans += diff[i] * (disc[i + 1] - disc[i]);
}
vector<array<int, 3>> edge;
for (int i = 1; i <= sz; i++) edge.push_back({i, i + 1, disc[i + 1] - disc[i]});
sort(edge.begin(), edge.end(), [] (auto x, auto y) {
return x[2] < y[2];
});
for (auto& [u, v, w] : edge) if (merge(u, v)) ans += w;
return ans;
}
