#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
struct UnionFind {
vector<int> p, sz;
UnionFind(int n) { p.assign(n,0); iota(ALL(p),0); sz.assign(n,1); }
int finds(int i) { return (p[i] == i) ? i : (p[i] = finds(p[i])); }
bool unions(int i, int j) {
int x = finds(i), y = finds(j);
if (x != y) {
if (sz[x] < sz[y]) swap(x,y);
p[y] = x, sz[x] += sz[y];
return true;
} return false;
}
};
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int N = SZ(s);
vector<int> vals;
for (int x : s) vals.push_back(x);
for (int x : t) vals.push_back(x);
sort(ALL(vals)); vals.resize(unique(ALL(vals))-vals.begin());
int V = SZ(vals);
int seg[V] = {0}; seg[0] = -1;
UnionFind UF(V);
FOR(i,0,N-1){
s[i] = lower_bound(ALL(vals),s[i])-vals.begin();
t[i] = lower_bound(ALL(vals),t[i])-vals.begin();
if (s[i] <= t[i]) ++seg[s[i]], --seg[t[i]];
else --seg[t[i]], ++seg[s[i]];
UF.unions(s[i],t[i]);
}
long long ans = 0;
vector<tuple<int,int,int>> el;
FOR(i,0,V-2){
if (i > 0) seg[i] += seg[i-1];
if (seg[i] != 0) {
ans += (long long) max(0,seg[i]) * (vals[i+1]-vals[i]);
UF.unions(i,i+1);
} else {
el.emplace_back(vals[i+1]-vals[i],i,i+1);
}
}
sort(ALL(el));
for (auto& [w,u,v] : el) if (UF.unions(u,v)) { ans += w; }
return ans;
}
