#include <bits/stdc++.h> using namespace std; struct segment { int ar[2]; }; const int N=2e5+1; int mast[N]; int mash[N]; int n,m; int pref_maxv[N]; int pref_min[N]; int ri[N]; int le[N]; int ind[N]; int am[N]; segment seg[4*N]; int up[N][21]; segment merge(segment a,segment b){ segment c; if(b.ar[1]>a.ar[1]){ c.ar[0]=a.ar[0]; } c.ar[1]=min(a.ar[1],b.ar[1]); return c; } void update(int v,int s,int e,int pos,int new_val){ if(s==e){ seg[v]={pos,new_val}; return; } int m=(s+e)/2; if(pos<=m){ update(2*v,s,m,pos,new_val); } else{ update(2*v+1,m+1,e,pos,new_val); } seg[v]=merge(seg[2*v],seg[2*v+1]); } segment get(int v,int s,int e,int l,int r){ if(l>r){ return {-1,-1}; } if(l==s && e==r){ return seg[v]; } int m=(l+r)/2; return merge(get(2*v,s,m,l,min(r,m)),get(2*v+1,m+1,e,max(m+1,l),r)); } int query(int s,int e){ int l=log2(e-s+1); return max(up[s][l],up[e-(1<<l)+1][l]); } void initialize(vector<int> t, vector<int> h) { n=t.size(); m=h.size(); pref_min[0]=1e9; for(int i=1;i<=n;++i){ mast[i]=t[i-1]; pref_maxv[i]=pref_maxv[i-1]; if(mast[pref_maxv[i]]<mast[i]){ pref_maxv[i]=i; } pref_min[i]=min(pref_min[i-1],mast[i]); } for(int i=1;i<=m;++i){ mash[i]=h[i-1]; up[i][0]=mash[i]; int l=1; int r=n; while(l<=r){ int mid=(l+r)/2; l=mid+1; if(pref_min[mid]>mash[i]){ am[i]=pref_maxv[mid]; } else{ r=mid-1; } } } for(int j=1;j<20;++j){ for(int i=1;i<=m;++i){ up[i][j]=max(up[i][j-1],up[i+(1<<(j-1))][j-1]); } } for(int i=m;i>0;--i){ int l=i+1; int r=m; ri[i]=i; while(l<=r){ int mid=(l+r)/2; if(query(i,mid)<mast[am[i]]){ l=mid+1; ri[i]=ri[get(1,1,m,i,mid).ar[0]]; } else{ r=mid-1; } } } for(int i=1;i<=m;++i){ int l=1; int r=i-1; le[i]=i; while(l<=r){ int mid=(l+r)/2; if(query(mid,i)<mast[am[i]]){ l=mid+1; le[i]=le[get(1,1,m,mid,i).ar[0]]; } else{ r=mid-1; } } } for(int i=1;i<=m;++i){ ind[i]=i; } for(int i=1;i<=m;++i){ ind[i]=ind[ri[le[i]]]; } } bool can_reach(int l, int r, int s, int d) { int mn=min(am[ind[s]],am[ind[d]]); if(am[get(1,1,m,min(s,d),max(s,d)).ar[0]]>=mn){ return 1; } return 0; }