#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)
#define f first
#define s second
const int N = 1 << 18;
int nxt[N], rnk[N];
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 = long long;
using pii = pair<int, int>;
using vi = vector<int>;
ll plan_roller_coaster(vi s, vi t) {
ll ans = 0;
int n = sz(s) + 1; s.eb(inf); t.eb(1);
vector<int> l(n), r(n);
vector<int> p = s;
p.insert(end(p), all(t));
sort(all(p)); p.erase(unique(all(p)), end(p));
rep(i, 0, n)
l[i] = lb(all(p), s[i]) - begin(p),
r[i] = lb(all(p), t[i]) - begin(p);
int m = sz(p); rep(u, 0, N) nxt[u] = -1;
rep(i, 0, n) unite(l[i], r[i]);
vector<int> sum(m--);
rep(i, 0, n) ++sum[l[i]], --sum[r[i]];
rep(i, 0, m) sum[i + 1] += sum[i];
vector<pii> e;
rep(i, 0, m) {
ll d = p[i + 1] - p[i];
if (sum[i]) {
unite(i + 1, i);
if (sum[i] > 0) ans += sum[i] * d;
} else e.eb(d, i);
}
sort(all(e));
trav(x, e) if (unite(x.s, x.s + 1)) ans += x.f;
return ans;
}
