#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin() , (x).end()
#define SZ(x) int(x.size())
#define sep ' '
const int MAXN = 5e5 + 10;
ll ps[MAXN];
vector<ll> compress;
ll plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size();
for(int i = 0 ; i < n ; i++){
compress.push_back(s[i]);
compress.push_back(t[i]);
}
sort(all(compress));
compress.resize(unique(all(compress)) - compress.begin());
for(int i = 0 ; i < n ; i++){
cout << s[i] << sep << t[i] << endl;
s[i] = lower_bound(all(compress) , s[i]) - compress.begin();
t[i] = lower_bound(all(compress) , t[i]) - compress.begin();
cout << s[i] << sep << t[i] << endl;
ps[s[i]]++; ps[t[i]]--;
}
ll ans = 0;
for(int i = 0 ; i + 1 < SZ(compress) ; i++){
ps[i + 1] += ps[i];
cout << i << sep << ps[i] << endl;
ans += max(0ll , ps[i] - 1) * (compress[i + 1] - compress[i]);
}
for(int i = 0 ; i < n ; i++){
if(ps[s[i]] <= 0) ans++;
}
return ans;
}
