#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int INF = 1e9;
int par[N * 2], cnt[N * 2];
int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
bool join(int u, int v) { u = find(u), v = find(v), par[u] = v; return u != v; }
struct Edge {
int w, u, v;
bool operator < (const Edge& rhs) const {
return w < rhs.w;
}
};
long long plan_roller_coaster(vector<int> s, vector<int> t) {
s.push_back(INF), t.push_back(1);
vector<int> vec;
for (auto i : s) vec.push_back(i);
for (auto i : t) vec.push_back(i);
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
int n = s.size(), m = vec.size();
for (int i = 0; i < m; ++i) par[i] = i;
for (int i = 0; i < n; ++i) {
s[i] = lower_bound(vec.begin(), vec.end(), s[i]) - vec.begin();
t[i] = lower_bound(vec.begin(), vec.end(), t[i]) - vec.begin();
if (s[i] < t[i]) cnt[s[i]]++, cnt[t[i]]--;
else cnt[t[i]]--, cnt[s[i]]++;
join(s[i], t[i]);
}
for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
long long res = 0;
for (int i = 0; i < m; ++i) {
if (cnt[i] < 0) join(i, i + 1);
if (cnt[i] > 0) {
join(i, i + 1), res += 1LL * cnt[i] * (vec[i + 1] - vec[i]);
}
}
vector<Edge> edge;
for (int i = 1; i < m; ++i) edge.push_back({vec[i] - vec[i - 1], i, i - 1});
sort(edge.begin(), edge.end());
for (auto i : edge) {
if (join(i.u, i.v)) res += i.w;
}
return res;
}
