#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define MAXN (int)2e5+5
using namespace std;
int n,m,t[MAXN],h[MAXN],l1[MAXN][25],l2[MAXN][25],lg[MAXN],k[MAXN],s[MAXN][25],p[MAXN][2];
int maxq(int l,int r){
int i=lg[r-l+1];
return max(s[l][i],s[r-(1<<i)+1][i]);
}
vector<pii>v;
void gp(int x,int j){
stack<int>s;
for(int i=1;i>=1&&i<=m;i+=x){
while(!s.empty()&&h[s.top()]>=h[i]){
s.pop();
}
p[i][j]=(s.empty()?-1:s.top());
s.push(i);
}
}
int lift(int x,int k,bool e){
for(int i=0;i<=lg[m];i++){
if((1<<i)&k){
if(e){x=l1[x][i];}
else{x=l2[x][i];}
}
}
return x;
}
void solve(){
for(int i=1;i<=m;i++){
s[i][0]=h[i];
}
for(int j=1;j<=lg[m];j++){
for(int i=1;(1<<(j-1))+i<=m;i++){
s[i][j]=max(s[i][j-1],s[i+(1<<(j-1))][j-1]);
}
}
gp(1,0);
gp(-1,1);
int ll=1e9;
for(int i=1;i<=n;i++){
ll=min(ll,t[i]);
if(v.empty()||v[v.size()-1].fi<t[i]){
v.emplace_back(t[i],ll);
}
}
for(int i=1;i<=m;i++){
int l=0,r=v.size()-1;k[i]=-1;
while(l<=r){
int s=(l+r)/2;
if(v[s].se<=h[i]){
r=s-1;
}else{
k[i]=s;
l=s+1;
}
}
if(k[i]==-1){continue;}
l=1,r=i;
int ans=i;
while(l<=r){
int s=(l+r)/2;
if(maxq(s,i)<v[k[i]].se){
ans=s;
r=s-1;
}else{
l=s+1;
}
}
if(ans>p[i][0]){continue;}
l1[i][0]=p[i][0];
for(int j=1;j<=lg[m];j++){
l1[i][j]=l1[l1[i-1][j-1]][j-1];
}
}for(int i=m;i>=1;i--){
if(k[i]==-1){continue;}
int l=i,r=m,ans=i;
while(l<=r){
int s=(l+r)/2;
if(maxq(i,s)<v[k[i]].se){
l=s+1;
ans=s;
}else{
r=s-1;
}
}
if(ans<p[i][1]||p[i][1]==-1){continue;}
l2[i][0]=p[i][1];
for(int j=1;j<=lg[m];j++){
l2[i][j]=l2[l2[i-1][j-1]][j-1];
}
}
}
int fnd(int l,int r,int s){
int tl=0,tr=s,ans=s;
while(tl<=tr){
int ts=(tl+tr)/2;
int x=lift(s,ts,1);
if(l<=x){
ans=x;
tl=ts+1;
}else{
tr=ts-1;
}
}
tl=0,tr=m-ans;
int ans2=ans;
while(tl<=tr){
int ts=(tl+tr)/2;
int x=lift(ans,ts,0);
if(r>=x&&x){
ans2=x;
tl=ts+1;
}else{
tr=ts-1;
}
}
return ans2;
}
void initialize(vector<int>T, vector<int>H){
for(int i=2;i<MAXN;i++){
lg[i]=lg[i/2]+1;
}
n=T.size(),m=H.size();
for(int i=1;i<=n;i++){
t[i]=T[i-1];
}for(int i=1;i<=m;i++){
h[i]=H[i-1];
}
solve();
}
bool can_reach(int L,int R,int S,int D){
++L;++R;++S;++D;
S=fnd(L,R,S);
D=fnd(L,R,D);
int db=min(v[k[S]].fi,v[k[D]].fi);
if(db>maxq(S,D)){
return 1;
}
return 0;
}
