#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(*max_element(AI(s)) + 10);
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();
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);
if (a <= b)
++pf[a], --pf[b];
else
++suf[b], --suf[a];
assert(a < m && b < m);
}
for (int i = 1;i < m;++i) pf[i] += pf[i-1];
for (int i = m-1;i >= 0;--i) suf[i] += suf[i+1];
ll res = 0;
for (int i = 0;i < m;++i) {
if (pf[i] != suf[i+1]) {
assert(i+1 < m);
D.M(i, i+1);
res += max(0, pf[i] - suf[i+1]) * 1ll * (lis[i+1] - lis[i]);
}
}
for (int i = 0;i < m;++i) {
if (D(i) != D(0)) return 1;
}
return res;
}
