#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 20;
const int maxn = 2e5 + 20;
pair<int, int> events[maxn * 2];
pair<int, int> len[maxn * 2];
int sum[maxn * 2];
int par[maxn * 2];
int depth[maxn * 2];
int root(int u) {
if (!par[u]) {
return u;
}
else {
return par[u] = root(par[u]);
}
}
bool update(int u, int v) {
int ru = root(u);
int rv = root(v);
if (ru == rv) {
return false;
}
if (depth[ru] > depth[rv]) {
swap(ru, rv);
}
par[ru] = rv;
if (depth[ru] == depth[rv]) {
depth[rv]++;
}
return true;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
s.push_back(inf);
t.push_back(1);
int n = s.size();
for (int i = 1; i <= n; i++) {
events[i * 2 - 1] = make_pair(s[i - 1], i);
events[i * 2] = make_pair(t[i - 1], -i);
}
s.resize(n + 1);
t.resize(n + 1);
sort(events + 1, events + n * 2 + 1);
int cnt = 0;
for (int i = 1; i <= n * 2; i++) {
if (events[i].first != events[i - 1].first) {
len[cnt] = make_pair(events[i].first - events[i - 1].first, cnt);
cnt++;
}
int id = events[i].second;
if (id > 0) {
s[id] = cnt;
}
else {
t[-id] = cnt;
}
}
for (int i = 1; i <= n; i++) {
update(s[i], t[i]);
sum[s[i]]++;
sum[t[i]]--;
}
long long res = 0;
for (int i = 1; i <= cnt - 1; i++) {
sum[i] += sum[i - 1];
if (sum[i] > 0) {
res += 1LL * len[i].first * sum[i];
}
if (sum[i]) {
update(i, i + 1);
}
}
sort(len + 1, len + cnt);
for (int i = 1; i <= cnt - 1; i++) {
if (update(len[i].second, len[i].second + 1)) {
res += len[i].first;
}
}
return res;
}
