#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
const int N = 2e5 + 5;
const int M = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;
int n;
vector<int> segTree(4*N); // Search by index
void build(int v, int tl, int tr, vector<pair<int, int>> &arr){
if(tl == tr){
segTree[v] = tl;
}else {
int tm = (tl + tr)/2;
build(v*2, tl, tm, arr);
build(v*2+1, tm+1, tr, arr);
segTree[v] = (arr[segTree[v*2+1]].s >= arr[segTree[v*2]].s)? segTree[v*2+1] : segTree[v*2];
}
}
void update(int v, int tl, int tr, int pos, vector<pair<int, int>> &arr){
if(tl == tr && tl == pos){
segTree[v] = n; // Means section used
}else {
int tm = (tl + tr)/2;
if(pos <= tm) update(v*2, tl, tm, pos, arr);
else update(v*2 + 1, tm+1, tr, pos, arr);
segTree[v] = (arr[segTree[v*2+1]].s >= arr[segTree[v*2]].s)? segTree[v*2+1] : segTree[v*2];
}
}
int query(int v, int tl, int tr, int l, int r, vector<pair<int, int>> &arr){
if(l > r) return 0;
if(tl == l && tr == r){
return segTree[v];
}else {
int tm = (tl + tr)/2;
int left = n, right = n;
if(l <= tm) left = query(v*2, tl, tm, l, min(tm, r), arr);
if(r >= tm + 1) right = query(v*2 + 1, tm + 1, tr, max(l, tm+1), r, arr);
return (arr[right].s >= arr[left].s)? right : left;
}
}
// Subtask 3
ll int plan_roller_coaster(vector<int> s, vector<int> t){
n = s.size();
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
v.PB(MP(t[i], s[i]));
}
sort(v.begin(), v.end());
v[n] = MP(-inf, -inf);
build(1, 0, n-1, v);
pair<int, int> cur = v[n-1];
update(1, 0, n-1, n-1, v);
for(int i = 1; i < n; i++){
// Find maximum s_next for eligible t_next
int idx = upper_bound(v.begin(), v.end(), MP(cur.s, inf)) - v.begin() - 1;
if(idx == -1) return 1; // No t smaller than current s
int nxt = query(1, 0, n-1, 0, idx, v);
if(nxt == n) return 1;
update(1, 0, n-1, nxt, v);
cur = v[nxt];
}
return 0;
}
// int main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// // ifstream cin();
// // ofstream cout();
// int temp;
// temp = plan_roller_coaster({1, 4, 5, 6}, {7, 3, 8, 6});
// cout << temp << endl;
// temp = plan_roller_coaster({3, 4, 7, 4}, {2, 7, 3, 5});
// cout << temp << endl;
// temp = plan_roller_coaster({100, 5, 5}, {4, 1, 101});
// cout << temp << endl;
// temp = plan_roller_coaster({3, 5, 5, 6}, {5, 4, 5, 7});
// cout << temp << endl;
// }
/*
1: (5, 1);
2: (100, 4);
3: (5, 101);
*/
