#include <algorithm>
#include <vector>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define sz(x) int((x).size())
#define eb(x...) emplace_back(x)
const int M = 1 << 19;
int nxt[M], rnk[M];
int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
u = head(u); v = head(v);
if (u == v) return false;
if (rnk[u] > rnk[v]) nxt[v] = u;
else {
nxt[u] = v;
if (rnk[u] == rnk[v]) ++rnk[v];
}
return true;
}
const int inf = 2e9;
using ll = int64_t;
using vi = vector<int>;
ll plan_roller_coaster(vi s, vi t) {
ll ans = 0;
s.eb(inf); t.eb(1); int n = sz(s);
vector<int> p = s; p.insert(end(p), all(t));
sort(all(p)); p.erase(unique(all(p)), end(p));
int m = sz(p); rep(u, 0, m) nxt[u] = -1;
vector<int> sum(m--);
rep(i, 0, n) {
int l = lb(all(p), s[i]) - begin(p), r = lb(all(p), t[i]) - begin(p);
unite(l, r);
++sum[l]; --sum[r];
}
rep(i, 0, m) sum[i + 1] += sum[i];
vector<int> e;
rep(i, 0, m) {
if (sum[i]) {
unite(i + 1, i);
if (sum[i] > 0) ans += 1ll * sum[i] * (p[i + 1] - p[i]);
} else e.eb(i);
}
sort(all(e), [&p](int u, int v){ return p[u + 1] - p[u] < p[v + 1] - p[v]; });
trav(u, e) if (unite(u, u + 1)) ans += p[u + 1] - p[u];
return ans;
}
