#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
using namespace std;
using ii = pair<int, int>;
int par[2*maxn];
struct edge {
int u, v, l;
edge() {}
edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}
bool operator < (const edge &other) const {
return l < other.l;
}
};
vector<edge> edges;
int find_set(int v) {
return par[v] < 0 ? v : par[v] = find_set(par[v]);
}
void union_set(int u, int v) {
u = find_set(u); v = find_set(v);
if (u == v) return;
if (par[u] < par[v]) swap(u, v);
par[v] += par[u];
par[u] = v;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
s.emplace_back(1e9);
t.emplace_back(1);
int n = s.size();
map<int, int> nho;
for (int i = 0; i < n; i++) {
++nho[s[i]];
--nho[t[i]];
}
int last = 0;
for (auto &i : nho) last = (i.se += last);
vector<int> a;
for (int i = 0; i < n; i++) {
a.emplace_back(s[i]);
a.emplace_back(t[i]);
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int m = a.size();
for (int i = 0; i < m; i++) par[i] = -1;
for (int i = 0; i < n; i++) {
int p = lower_bound(a.begin(), a.end(), s[i]) - a.begin(),
q = lower_bound(a.begin(), a.end(), t[i]) - a.begin();
union_set(p, q);
}
int64_t ans = 0;
for (auto &i : nho)
if (i.se > 0) {
int p = lower_bound(a.begin(), a.end(), i.fi) - a.begin();
ans += 1LL * (a[p+1] - a[p]) * i.se;
union_set(p+1, p);
i.se = 0;
}
for (auto [u, v] : nho)
if (v < 0) {
int p = lower_bound(a.begin(), a.end(), u) - a.begin();
union_set(p, p+1);
}
for (int i = 0; i < m-1; i++) edges.emplace_back(i, i+1, a[i+1]-a[i]);
sort(edges.begin(), edges.end());
for (auto [u, v, l] : edges)
if (find_set(u) != find_set(v)) {
union_set(u, v);
ans += l;
}
return ans;
}
