#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 1e9;
int n;
int par[2*maxn], degIn[2*maxn], degOut[2*maxn];
int get_par(int v){
return par[v] < 0 ? v : par[v] = get_par(par[v]);
}
bool merge(int v, int u){
if (get_par(v) == get_par(u))
return false;
par[v] = u;
return true;
}
ll plan_roller_coaster(vector<int> s, vector<int> t){
s.push_back(inf);
t.push_back(1);
n = s.size();
vector<int> Cmp;
for (auto it : s) Cmp.push_back(it);
for (auto it : t) Cmp.push_back(it);
sort(Cmp.begin(), Cmp.end());
Cmp.resize(unique(Cmp.begin(), Cmp.end())-Cmp.begin());
memset(par, -1, sizeof par);
for (int i = 0; i < n; i++){
s[i] = lower_bound(Cmp.begin(), Cmp.end(), s[i]) - Cmp.begin();
t[i] = lower_bound(Cmp.begin(), Cmp.end(), t[i]) - Cmp.begin();
merge(t[i],s[i]);
degOut[s[i]] ++, degIn[t[i]] ++;
}
int m = Cmp.size();
ll untilNow = 0;
for (int i = 0; i < m-1; i++){
int diff = abs(degIn[i]-degOut[i]);
if (diff > 0)
merge(i,i+1);
if (degIn[i] < degOut[i]){
degIn[i] += diff;
degOut[i+1] += diff;
untilNow += 1LL*diff*(Cmp[i+1]-Cmp[i]);
}
else{
degOut[i] += diff;
degIn[i+1] += diff;
}
}
vector<pair<int,pair<int,int>>> E;
for (int i = 0; i < m-1; i++)
if (get_par(i) != get_par(i+1))
E.push_back({Cmp[i+1]-Cmp[i],{get_par(i),get_par(i+1)}});
sort(E.begin(),E.end());
for (auto it : E){
int v = it.second.first, u = it.second.second;
if (merge(v,u))
untilNow += it.first;
}
return untilNow;
}
