#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];
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){
R=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])});
}
}
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);
par[i]=Get(root,0,m-1,seg.first,seg.second).second;
}else{
myMx[i]=-1;
par[i]=i;
}
}
sort(ord.begin(),ord.end(),[&](int i,int j){return H[i]<H[j];});
for(int i:ord){
par[i]=par[par[i]];
}
}
bool can_reach(int L, int R, int S, int D) {
S=par[S];
D=par[D];
int mx=min(myMx[S],myMx[D]);
return Get(min(S,D),max(S,D))<mx;
}
