#include "railroad.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;
typedef vector < int > vi;
ll n, m, ans, fen[N], ne[N], ata[N];
map < ll , ll > h, hh;
map < ll , ll > :: iterator it;
ii a[N];
ll atabul(ll x){return ata[x] = (ata[x]==x)?x:atabul(ata[x]);}
void upp(ll x, ll y){
for(; x < N; x += x&-x)
fen[x] += y;
}
void up(ll x, ll y, ll z){
upp(x, z);
upp(y + 1, -z);
}
ll qu(ll x){
ll ans = 0;
for(; x > 0; x -= x&-x)
ans += fen[x];
return ans;
}
ll plan_roller_coaster(vi x, vi y) {
x.pb(inf);y.pb(1);
n = (int)x.size();x.insert(x.begin(), 0);y.insert(y.begin(), 0);
hh[inf]++;
for(ll i = 1; i <= n; i++){
hh[x[i]]++;
hh[y[i]]++;
}
for(it = hh.begin(); it != hh.end(); it++){
h[it->st] = ++m;
ne[m] = it->st;
ata[m] = m;
}
for(ll i = 1; i <= n; i++){
// cout << h[x[i]] << " " << h[y[i]] << endl;
ll xx = atabul(h[x[i]]);
ll yy = atabul(h[y[i]]);
if(xx != yy)
ata[xx] = yy;
if(x[i] < y[i])
up(h[x[i]] + 1, h[y[i]], 1);
else if(y[i] < x[i])
up(h[y[i]] + 1, h[x[i]], -1);
}
for(ll i = 1; i <= m; i++){
if(qu(i) > 0){
// cout << i << " " << qu(i) << endl;
ll xx = atabul(i);
ll yy = atabul(i - 1);
if(xx != yy)
ata[xx] = yy;
ans += ne[i] - ne[i - 1];
} else if(qu(i) < 0){
ll xx = atabul(i);
ll yy = atabul(i - 1);
if(xx != yy)
ata[xx] = yy;
}
if(i >= 2)
a[i] = mp(ne[i] - ne[i - 1], i);
// cout << "ve " << ne[i] << " " << qu(i) - 1 << endl;
}
sort(a + 2, a + m + 1);
for(ll i = 2; i <= m; i++){
ll j = a[i].nd;
ll xx = atabul(j);
ll yy = atabul(j - 1);
if(xx != yy){
ata[xx] = yy;
if(j != m)
ans += ne[j] - ne[j - 1];
// cout << ne[j] - ne[j - 1] << " eklendi" << endl;
}
}
return ans;
}
