#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=200050;
const int LOG=20;
int rmq[N][LOG];
int par[N][LOG];
int rpar[N][LOG];
int lpar[N][LOG];
pair<int,int> rng[N];
int myMx[N];
const int inf=1e9+7;
const int M=2*N;
int ls[M],rs[M],tsz,root;
pair<int,int> mn[M];
void Build(int&c,int ss,int se,vector<int>&H){
c=++tsz;
if(ss==se){
mn[c]={H[ss],ss};
return;
}
int mid=ss+se>>1;
Build(ls[c],ss,mid,H);
Build(rs[c],mid+1,se,H);
mn[c]=min(mn[ls[c]],mn[rs[c]]);
}
pair<int,int> Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qs>se||ss>qe)return {inf,-1};
if(qs<=ss&&qe>=se)return mn[c];
int mid=ss+se>>1;
return min(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
void BuildRMQ(vector<int> H){
int n=H.size();
for(int i=0;i<n;i++){
rmq[i][0]=H[i];
}
for(int j=1;j<LOG;j++){
for(int i=0;i<n-(1<<j)+1;i++){
rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
}
}
Build(root,0,n-1,H);
}
int Get(int l,int r){
int k=31-__builtin_clz(r-l+1);
return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
pair<int,int> GetRange(int n,int i,int mn){
int top=n-1,bot=i,R=i;
while(top>=bot){
int mid=top+bot>>1;
if(Get(i,mid)<mn){
R=mid;
bot=mid+1;
}else{
top=mid-1;
}
}
top=i,bot=0;
int L=i;
while(top>=bot){
int mid=top+bot>>1;
if(Get(mid,i)<mn){
L=mid;
top=mid-1;
}else{
bot=mid+1;
}
}
return {L,R};
}
void initialize(vector<int> T, vector<int> H) {
int n=T.size();
int m=H.size();
vector<pair<int,int>> rngs;
for(int i=0;i<n;i++){
if(rngs.empty()){
rngs.pb({T[i],T[i]});
}else{
rngs.pb({min(rngs.back().first,T[i]),max(rngs.back().second,T[i])});
}
}
BuildRMQ(H);
vector<int> ord;
for(int i=0;i<m;i++){
ord.pb(i);
int top=(int)rngs.size()-1,bot=0,best=-1;
while(top>=bot){
int mid=top+bot>>1;
if(rngs[mid].first>H[i]){
best=mid;
bot=mid+1;
}else{
top=mid-1;
}
}
if(best!=-1){
myMx[i]=rngs[best].second;
pair<int,int> seg=GetRange(m,i,rngs[best].second);
//printf("range(%i) = %i %i\n",i,seg.first,seg.second);
lpar[i][0]=Get(root,0,m-1,seg.first,i).second;
par[i][0]=Get(root,0,m-1,seg.first,seg.second).second;
rpar[i][0]=Get(root,0,m-1,i,seg.second).second;
rng[i]=seg;
}else{
rng[i]={i,i};
myMx[i]=-1;
par[i][0]=i;
lpar[i][0]=i;
rpar[i][0]=i;
}
//printf("%i: myMx:%i par:%i lpar:%i rpar:%i rng:(%i, %i)\n",i,myMx[i],par[i][0],lpar[i][0],rpar[i][0],rng[i].first,rng[i].second);
}
sort(ord.begin(),ord.end(),[&](int i,int j){return H[i]<H[j];});
for(int i:ord){
for(int j=1;j<LOG;j++){
lpar[i][j]=lpar[lpar[i][j-1]][j-1];
par[i][j]=par[par[i][j-1]][j-1];
rpar[i][j]=rpar[rpar[i][j-1]][j-1];
}
//printf("%i: root:%i\n",i,par[i][0]);
}
}
bool Inside(int L,int R,pair<int,int> a){
return L<=a.first && R>=a.second;
}
int Lift(int u,int L,int R){
for(int i=LOG-1;i>=0;i--){
//if(Inside(L,R,rng[par[u][i]])){
u=par[u][i];
//}
}
return u;
/*if(Inside(L,R,{par[u][0],par[u][0]})){
u=par[u][0];
}
int l=u,r=u;
for(int i=LOG-1;i>=0;i--){
//printf("%i ",lpar[l][i]);
if(lpar[l][i]>=L){
l=lpar[l][i];
}
if(rpar[r][i]<=R){
r=rpar[r][i];
}
}
//printf("l:%i r:%i\n",l,r);
return myMx[l]<myMx[r]?r:l;*/
}
bool can_reach(int L, int R, int S, int D) {
//printf("L:%i R:%i S:%i D:%i\n",L,R,S,D);
S=Lift(S,L,R);
D=Lift(D,L,R);
//printf("Lift(S):%i Lift(D):%i\n",S,D);
int mx=min(myMx[S],myMx[D]);
return Get(min(S,D),max(S,D))<mx;
}
