#include "obstacles.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9;
struct table
{
pii min_[200001][18];
pii max_[200001][18];
void set(vi v)
{
rep(i,siz(v))
{
min_[i][0] = {v[i],i};
max_[i][0] = {v[i],i};
}
rep2(bit,1,17)
{
rep(i,siz(v))
{
min_[i][bit] = min(min_[i][bit-1],(i+(1<<(bit-1)) < siz(v) ? min_[i+(1<<(bit-1))][bit-1] : (pii){1e9,1e9}));
max_[i][bit] = max(max_[i][bit-1],(i+(1<<(bit-1)) < siz(v) ? max_[i+(1<<(bit-1))][bit-1] : (pii){-1e9,-1e9}));
}
}
}
pii get_max(int l, int r)
{
int lg = __lg(r-l+1);
return max(max_[l][lg],max_[r-(1 << lg)+1][lg]);
}
pii get_min(int l, int r)
{
int lg = __lg(r-l+1);
return min(min_[l][lg],min_[r-(1 << lg)+1][lg]);
}
};
table tableX;
table tableY;
int max_H[200001];
int X[200001];
int Y[200001];
vi pref;
void split(int l, int r, int h, vector<pii>& ans)
{
if(l > r) return;
int max_col = tableX.get_max(l,r).ss;
if(Y[h] > X[max_col]) ans.pb({l,r});
else
{
split(l,max_col-1,h,ans);
split(max_col+1,r,h,ans);
}
}
void rek(int l, int r, int pref_max, int pop)
{
cerr << l << " " << r << " " << pref_max << " " << pop << " rek\n";
int max_col = tableX.get_max(l,r).ss;
int l2 = 0;
int r2 = pref_max;
int down_ok = pref_max;
while(l2 <= r2)
{
int mid = (l2+r2)/2;
if(Y[pref[mid]] > X[max_col])
{
down_ok = mid;
r2 = mid-1;
}
else
{
l2 = mid+1;
}
}
cerr << down_ok << " ok\n";
vector<pii> segs;
if(down_ok != 0) split(l,r,pref[down_ok-1],segs);
else segs.pb({l,r});
int pop2 = pop;
if(down_ok != pref_max)
{
int l2 = down_ok;
int r2 = pref_max;
int up = down_ok;
int min_col = tableX.get_min(l,r).ss;
while(l2 <= r2)
{
int mid = (l2+r2)/2;
if(tableY.get_min(pref[down_ok],pref[mid]).ff > X[min_col])
{
up = mid;
l2 = mid+1;
}
else
{
r2 = mid-1;
}
}
cerr << up << " up\n";
if(up != pref_max)
{
pop2 = pref[up];
}
}
if(down_ok == 0)
{
rep2(i,l,r)
{
max_H[i] = pop2;
}
return;
}
forall(it,segs)
{
if(tableY.get_min(pref[down_ok-1],pref[down_ok]).ff > tableX.get_min(it.ff,it.ss).ff)
{
rek(it.ff,it.ss,down_ok-1,pop2);
}
else
{
rek(it.ff,it.ss,down_ok-1,down_ok-1);
}
}
}
void initialize(vi T, vi H)
{
T.pb(-1);
rep(i,siz(T)) Y[i] = T[i];
rep(i,siz(H)) X[i] = H[i];
tableY.set(T);
tableX.set(H);
int pop = -1;
rep(i,siz(T))
{
if(Y[i] >= pop)
{
pref.pb(i);
pop = Y[i];
}
}
rek(0,siz(H)-1,siz(pref)-1,pref.back());
}
bool can_reach(int L, int R, int S, int D)
{
int row = min(max_H[S],max_H[D]);
if(D > S) swap(D,S);
return tableX.get_max(D,S).ff < Y[row];
}
