#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<
using llint = long long;
int n, m;
llint sol;
vector<int> v;
map<int, int> deg, dad, open;
int find(int x) {
if (dad.find(x) == dad.end()) return dad[x] = x;
if (dad[x] == x) return x;
return dad[x] = find(dad[x]);
}
void unite(int x, int y) {
if (rand() % 2)
dad[find(x)] = find(y);
else
dad[find(y)] = find(x);
}
llint plan_roller_coaster(vector<int> s, vector<int> t) {
srand(time(NULL));
m = (int)s.size();
for (int i = 0; i < m; ++i) {
v.emplace_back(s[i]);
v.emplace_back(t[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
n = (int)v.size();
s.emplace_back(v[n - 1]);
t.emplace_back(v[0]);
++m;
for (int i = 0; i < m; ++i) {
deg[s[i]]++; deg[t[i]]--;
unite(s[i], t[i]);
}
vector<pair<int, int>> e;
for (int i = 0; i < n - 1; ++i) {
if (i != 0) open[v[i]] = open[v[i - 1]];
open[v[i]] += deg[v[i]];
if (open[v[i]] == 0) {
e.emplace_back(v[i], v[i + 1]);
continue;
}
unite(v[i], v[i + 1]);
if (open[v[i]] > 0)
sol += (llint) open[v[i]] * (v[i + 1] - v[i]);
}
sort(e.begin(), e.end(),
[](const pair<int, int> &A, const pair<int, int> &B) {
return A.second - A.first < B.second - B.first;
});
for (const auto &p : e) {
if (find(p.first) == find(p.second)) continue;
sol += (llint) p.second - p.first;
unite(p.first, p.second);
}
return sol;
}
