#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
#define vec vector
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = s.size();
vec<pair<int, int>> vs(n);
vec<pair<int, int>> vt(n);
for(int i = 0; i<n; i++) {
vs[i] = {s[i], i};
vt[i] = {t[i], i};
//cerr << s[i] << ' ';
}
//ncerr << '\n';
sort(vs.begin(), vs.end());
sort(vt.begin(), vt.end());
vec<pair<int, int>> se(0);
if(vs[0].second == vt[n-1].second) {
se.push_back({vs[0].second, vt[n-2].second});
se.push_back({vs[1].second, vt[n-1].second});
}
else {
se.push_back({vs[0].second, vt[n-1].second});
}
bool ans = false;
for(auto [si, ei] : se) {
int j = 0;
set<int> reach;
bool ok = true;
for(int i = 0; i<n; i++) {
// cerr << "----------------" << i << '\n';
while(j<n && vt[j].first <= vs[i].first) {
if(vt[j].second != ei) {
reach.insert(vt[j].second);
}
// cerr << vt[j].first << ": " << "shifting" << '\n';
j++;
}
if(vs[i].second != si) {
auto it = reach.begin();
if(it == reach.end()) {
ok = false;
break;
}
if(*it == vs[i].second) it++;
if(it == reach.end()) {
ok = false;
break;
}
reach.erase(it);
}
// cerr << bal << '\n';
}
ans |= ok;
}
if(ans) return 0;
else return 1;
}
