#include <bits/stdc++.h>
using namespace std;
struct segment
{
int ar[2];
};
const int N=2e5+1;
const int inf=1e9;
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];
}
else{
c.ar[0]=b.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,inf};
}
if(l==s && e==r){
return seg[v];
}
int mid=(s+e)/2;
return merge(get(2*v,s,mid,l,min(r,mid)),get(2*v+1,mid+1,e,max(mid+1,l),r));
}
int query(int s,int e){
int l=31-__builtin_clz(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<4*N;++i){
seg[i]={-1,inf};
}
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];
update(1,1,m,i,mash[i]);
int l=1;
int r=n;
while(l<=r){
int mid=(l+r)/2;
if(pref_min[mid]>mash[i]){
am[i]=pref_maxv[mid];
l=mid+1;
}
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[min(N-1,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]]){
r=mid-1;
le[i]=le[get(1,1,m,mid,i).ar[0]];
}
else{
l=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]]];
}
}
int id(int v){
int g=am[v];
int s=v;
int e=v;
while(true){
int f=g;
for(int i=e+1;i<=m;++i){
if(mast[g]<=mash[i]){
break;
}
e=i;
g=max(g,am[i]);
}
for(int i=s-1;i>=le[i];--i){
s=i;
g=max(g,am[i]);
}
if(f==g){
break;
}
}
return g;
}
bool can_reach(int l, int r, int s, int d) {
s++;
d++;
int u=id(s);
int g=id(d);
int x=min(u,g);
for(int i=min(s,d);i<=max(s,d);++i){
if(mast[x]<=mash[i]){
return 0;
}
}
return 1;
}
