#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct segment { int ar[2]; }; const int N=3e5+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]){ return a; } return b; } 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=log2(e-s+1); return max(up[s][l],up[e-(1<<l)+1][l]); } 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>0;--i){ if(mast[g]<=mash[i]){ break; } s=i; g=max(g,am[i]); } if(f==g){ break; } } return g; } 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[le[ri[i]]]; } } bool can_reach(int l, int r, int s, int d) { s++; d++; int mn=min(am[ind[s]],am[ind[d]]); int x=min(s,d); int y=max(s,d); if(query(x,y)<mast[mn]){ return 1; } return 0; } bool can_reach1(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; }