#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pair;
const int Nmax = 4e5 + 5, lim = 1e9;
int n, len[Nmax], t[Nmax], comp[Nmax], balance[Nmax];
map<int, int> mp;
vector<int> v[Nmax];
vector< pair<int, Pair> > edge;
void dfs(int node, int c)
{
comp[node] = c;
for(auto it : v[node])
if(!comp[it]) dfs(it, c);
}
void add_edge_for_apm(int x, int y, int cost)
{
edge.push_back({ cost, {x, y} });
}
void add_edge(int x, int y)
{
v[x].push_back(y);
v[y].push_back(x);
}
int boss(int x)
{
if(x == t[x]) return x;
return t[x] = boss(t[x]);
}
void unite(int x, int y)
{
t[t[x]] = t[y];
}
void APM(ll &ans, int n)
{
int i;
for(i=1; i<=n; ++i) t[i] = i;
sort(edge.begin(), edge.end());
int x, y, cost;
for(auto it : edge)
{
x = it.second.first;
y = it.second.second;
cost = it.first;
if(boss(x) == boss(y)) continue;
ans += cost;
unite(x, y);
}
}
ll plan_roller_coaster(vector<int> s, vector<int> t)
{
s.push_back(lim);
t.push_back(1);
for(auto it : s) mp[it] ++;
for(auto it : t) mp[it] --;
int n = 0, sum = 0, prv = 0;
for(auto &it : mp)
{
sum += it.second;
len[n] = it.first - prv;
balance[++n] = sum;
it.second = n;
prv = it.first;
}
ll ans = 0;
int i;
for(i=1; i<n; ++i)
if(balance[i])
{
ans += (ll) len[i] * max(0, balance[i]);
add_edge(i, i+1);
}
for(i=0; i<s.size(); ++i)
add_edge(mp[s[i]], mp[t[i]]);
int Comp = 0;
for(i=1; i<=n; ++i)
if(!comp[i])
dfs(i, ++Comp);
for(i=1; i<n; ++i)
add_edge_for_apm(comp[i], comp[i+1], len[i]);
APM(ans, Comp);
return ans;
}
