#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]);
}
};
struct jump_str
{
int l,r,v;
jump_str operator+(const jump_str& other)
{
jump_str res;
res.l = min(l,other.l);
res.r = max(r,other.r);
res.v = other.v;
return res;
}
};
table tableX;
table tableY;
jump_str jump[500001][18];
int vert[200001];
int X[200001];
int Y[200001];
vi pref;
int cur_v = 0;
int vH[500001];
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);
}
}
jump_str get_jump(int l, int r, int h, int prev)
{
jump_str j = {(int)1e9,(int)-1e9,prev};
int pop_H = vH[prev];
int l2 = l;
int r2 = r;
while(l2 <= r2)
{
int mid = (l2+r2)/2;
if(tableX.get_min(mid,r).ff < tableY.get_min(h,pop_H).ff)
{
j.l = mid;
l2 = mid+1;
}
else
{
r2 = mid-1;
}
}
l2 = l;
r2 = r;
while(l2 <= r2)
{
int mid = (l2+r2)/2;
if(tableX.get_min(l,mid).ff < tableY.get_min(h,pop_H).ff)
{
j.r = mid;
r2 = mid-1;
}
else
{
l2 = mid+1;
}
}
return j;
}
void rek(int l, int r, int pref_max, int pop)
{
int v = cur_v++;
vH[v] = pref[pref_max];
if(pop != -1) jump[v][0] = get_jump(l,r,pref[pref_max],pop);
else jump[v][0] = {(int)1e9,(int)-1e9,v};
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;
}
}
vector<pii> segs;
if(down_ok != 0) split(l,r,pref[down_ok-1],segs);
else segs.pb({l,r});
int v_down = cur_v++;
vH[v_down] = pref[down_ok];
if(down_ok != pref_max)
{
if(tableY.get_min(pref[down_ok],pref[pref_max]).ff <= tableX.get_min(l,r).ff)
{
jump[v_down][0] = {(int)1e9,(int)-1e9,v_down};
}
else
{
jump[v_down][0] = get_jump(l,r,pref[down_ok],v);
}
}
else
{
jump[v_down][0] = {(int)1e9,(int)-1e9,v};
}
if(down_ok == 0)
{
rep2(i,l,r)
{
vert[i] = v_down;
}
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,v_down);
}
else
{
rek(it.ff,it.ss,down_ok-1,-1);
}
}
}
void initialize(vi T, vi H)
{
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];
}
}
vH[0] = pref.back();
rek(0,siz(H)-1,siz(pref)-1,-1);
rep2(bit,1,17)
{
rep(i,cur_v)
{
jump[i][bit] = jump[i][bit-1] + jump[jump[i][bit-1].v][bit-1];
}
}
}
bool can_reach(int L, int R, int S, int D)
{
if(S > D) swap(D,S);
int v1 = vert[S];
int v2 = vert[D];
for(int bit = 17; bit >= 0; bit--)
{
if(jump[v1][bit].l >= L)
{
v1 = jump[v1][bit].v;
}
if(jump[v2][bit].r <= R)
{
v2 = jump[v2][bit].v;
}
}
int row = min(vH[v1],vH[v2]);
return tableX.get_max(S,D).ff < Y[row];
}
