#include "railroad.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
const int MAXN = 2e5+5;
ll inf = 1e18;
int n;
vector<int> s, t;
vector<int> edges[MAXN], rev[MAXN];
vector<int> all;
int used[MAXN];
struct segtree{
int sz;
vector<int> t;
void init(int n){
sz = n;
t.assign(n*2,0);
}
void update(int l, int r, int val){
assert(l <= r);
for(l+=sz,r+=sz; l<=r; l>>=1,r>>=1){
if(l%2==1)t[l++] += val;
if(r%2==0)t[r--] += val;
}
return;
}
int get(int pos){
int res = 0;
for(pos += sz; pos > 0; pos >>= 1)res += t[pos];
return res;
}
}seg;
int pos[MAXN];
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
s = sk, t = tk;
n = s.size();
seg.init(n*2);
for(int i=0;i<n;i++){
all.push_back(s[i]);
all.push_back(t[i]);
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(),all.end()),all.end());
vector<int> v;
for(int i=0;i<n;i++){
v.push_back(s[i]);
v.push_back(t[i]);
}sort(v.begin(), v.end());
for(int i=0;i<n;i++){
s[i] = lower_bound(v.begin(), v.end(), s[i])-v.begin();
t[i] = lower_bound(v.begin(), v.end(), t[i])-v.begin();
if(s[i] < t[i]){
seg.update(s[i], t[i]-1, 1);
}else if(s[i] > t[i]){
seg.update(t[i], s[i]-1, -1);
}edges[s[i]].push_back(t[i]);
}
edges[n-1].push_back(0);
seg.update(0,n-1,-1);
for(int i=0;i<n-1;i++){
if(seg.get(i) > 0){
return 1000000000;
}if(seg.get(i) < 0){
edges[i].push_back(i+1);
}
}
/// check for connectivity
queue<int> q;
q.push(0);
used[0] = true;
while(!q.empty()){
int u = q.front();q.pop();
for(auto v : edges[u]){
if(!used[v]){
q.push(v);used[v] = true;
}
}
}
for(int i=0;i<n;i++){
if(!used[i])return 987654321;
}
for(int i=0;i<n;i++){
for(auto v : edges[i]){
rev[v].push_back(i);
}
}
//~ memset(used, 0, sizeof used);
//~ q.push(0);
//~ used[0] = true;
//~ while(!q.empty()){
//~ int u = q.front();q.pop();
//~ for(auto v : rev[u]){
//~ if(!used[v]){
//~ q.push(v);used[v] = true;
//~ }
//~ }
//~ }
//~ for(int i=0;i<n;i++){
//~ if(!used[i])return 123456789;
//~ }
/// check for eulerian circuit
for(int i=0;i<n;i++){
ll s1 = edges[i].size(), s2 = rev[i].size();
if(s1 != s2)return 999999999;
}
return 0;
}
