#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e9;
lint plan_roller_coaster(vector<int> s, vector<int> t) {
s.emplace_back(INF), t.emplace_back(1);
int N = s.size(), M;
vector<int> coord, flow;
vector<tuple<int, int, int>> edges; // tuple < cost, endpoint 1, endpoint 2 >
lint res = 0;
/* Coordinate compressions */
auto get_pos = [&] (int n) {
return lower_bound(coord.begin(), coord.end(), n) - coord.begin();
};
for (int i = 0; i < N; i++)
coord.emplace_back(s[i]), coord.emplace_back(t[i]);
sort(coord.begin(), coord.end());
coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
M = coord.size(), flow.resize(M);
for (int i = 0; i < N; i++) {
s[i] = get_pos(s[i]), t[i] = get_pos(t[i]);
flow[s[i]]++, flow[t[i]]--; // if s[i] < t[i], [s[i], t[i]) + 1, else [s[i], t[i]) - 1
edges.emplace_back(0, s[i], t[i]);
}
for (int i = 1; i < M; i++)
flow[i] += flow[i - 1];
for (int i = 0; i < M - 1; i++) {
res += max(0ll, (lint)flow[i] * (coord[i + 1] - coord[i]));
if (flow[i] == 0)
edges.emplace_back(coord[i + 1] - coord[i], i, i + 1);
else
edges.emplace_back(0, i, i + 1);
}
/* Disjoint Set Union Find Data Structure */
vector<int> par(M);
iota(par.begin(), par.end(), 0);
auto find = [&](int n) {
auto lambda = [&](int n, const auto &lambda) {
if (par[n] == n) return n;
return par[n] = lambda(par[n], lambda);
};
return lambda(n, lambda);
};
/* Minimum Spanning Tree */
sort(edges.begin(), edges.end());
for (auto e : edges) {
if (find(get<1>(e)) != find(get<2>(e))) {
res += get<0>(e);
par[find(get<1>(e))] = find(get<2>(e));
}
}
return res;
}
