#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
long long plan_roller_coaster(vector<int> s, vector<int> t){
#define i64 long long
int n = s.size();
vector<array<int, 2>> a(n + 1);
vector<int> comp;
comp.push_back(1);
for(int i = 1; i <= n; ++i){
a[i][0] = s[i - 1], a[i][1] = t[i - 1];
comp.push_back(a[i][0]);
comp.push_back(a[i][1]);
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
int k = comp.size();
map<int, int> idx;
for(int i = 0; i < k; ++i) idx[comp[i]] = i;
vector<int> pa(k + 5);
iota(pa.begin(), pa.end(), 0);
auto fp = [&](auto &&fp, int u) -> int {
if(pa[u] == u) return u;
return pa[u] = fp(fp, pa[u]);
};
vector<i64> sweep(k + 5, 0);
for(int i = 1; i <= n; ++i){
int u = idx[a[i][0]], v = idx[a[i][1]];
sweep[v] += 1; sweep[u] -= 1;
pa[fp(fp, v)] = fp(fp, u);
}
sweep[idx[1]] += 1;
i64 ans = 0, p = 0;
vector<tuple<i64, int, int>> edge;
for(int i = 0; i < k - 1; ++i){
p += sweep[i];
if(p > 0) pa[fp(fp, i + 1)] = fp(fp, i);
else if(p < 0){
ans += (-p)*(comp[i + 1] - comp[i]);
pa[fp(fp, i + 1)] = fp(fp, i);
}
else edge.emplace_back(comp[i + 1] - comp[i], i, i + 1);
}
sort(edge.begin(), edge.end());
for(auto [w, u, v]:edge){
if(fp(fp, u) != fp(fp, v)){
pa[fp(fp, v)] = fp(fp, u);
ans += w;
}
}
return ans;
}
