#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
const ll inf = 1ll << 55;
#include "railroad.h"
struct dsu {
vector<int> g, sz;
int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
int operator()(int i) { return F(i); }
bool M(int a, int b) {
a = F(a), b = F(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
return sz[a] += sz[b], g[b] = a, true;
}
dsu(int n) {
g.resize(n + 10), sz.resize(n + 10, 1);
iota(AI(g), 0);
}
};
struct lisan : vector<int> {
void done() { sort(AI()), erase(unique(AI()), end()); }
int operator ()(int i) {
return lower_bound(AI(), i) - begin();
}
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = (int) s.size() + 1;
s.pb(1e9);
t.pb(1);
lisan lis;
for (int i = 0;i < n;++i) {
lis.pb(s[i]), lis.pb(t[i]);
}
lis.done();
int m = lis.size();
for (int i = 1;i < m;++i) assert(lis[i] > lis[i-1]);
dsu D(m);
vector<int> pf(m + 10), suf(m + 10);
for (int i = 0;i < n;++i) {
int a = lis(s[i]), b = lis(t[i]);
D.M(a, b);
++pf[a], --pf[b];
assert(a < m && b < m);
}
for (int i = 1;i <= m;++i) pf[i] += pf[i-1];
ll res = 0;
for (int i = 0;i < m;++i) {
if (pf[i] != 0) {
assert(i+1 < m);
D.M(i, i+1);
res += max(0, pf[i]) * 1ll * (lis[i+1] - lis[i]);
}
}
vector<pair<int,int>> alle;
for (int i = 0;i+1 < m;++i) if (D(i) != D(i+1)) {
alle.pb(lis[i+1] - lis[i], i);
}
sort(AI(alle));
for (auto [w, i] : alle)
if (D.M(i, i+1))
res += w;
return res;
}
