#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
vector<ll>t,h, seg, I, D;
vector<pair<ll,ll>>seg2;
ll n, m, pot=1;
void initialize(std::vector<int> T, std::vector<int> H) {
for(auto k:T)
t.pb(k);
for(auto k:H)
h.pb(k);
while(pot<sz(h))
pot*=2;
seg.resize(pot*2,0);
seg2.resize(pot*2,{LLONG_MAX,-1});
I.resize(pot*2);
D.resize(pot*2);
ll i;
for(i=pot; i<pot*2; i++)
I[i]=D[i]=i;
for(i=0; i<sz(H); i++)
{
seg[i+pot]=H[i];
seg2[i+pot]={H[i],i};
}
for(i=pot-1; i>0; i--)
{
I[i]=I[i*2];
D[i]=D[i*2+1];
seg[i]=max(seg[i*2],seg[i*2+1]);
seg2[i]=seg2[i*2];
if(seg2[i*2+1].fr<seg2[i].fr)
seg2[i]=seg2[i*2+1];
}
return;
}
ll calc(ll a, ll b, ll nod)
{
if(I[nod]>b||D[nod]<a)
return 0;
if(I[nod]>=a&&D[nod]<=b)
return seg[nod];
return max(calc(a,b,nod*2),calc(a,b,nod*2+1));
}
pair<ll,ll> calc2(ll a, ll b, ll nod)
{
if(I[nod]>b||D[nod]<a)
return {LLONG_MAX,-1};
if(I[nod]>=a&&D[nod]<=b)
return seg2[nod];
pair<ll,ll>r1,r2;
r1=calc2(a,b,nod*2);
r2=calc2(a,b,nod*2+1);
if(r1.fr>r2.fr)
return r2;
return r1;
}
bool con(ll i, ll ja, ll jb)
{
ll ma=0, j;
ma=calc(ja+pot,jb+pot,1);
if(ma>=t[i])
return 0;
return 1;
}
ll minR(ll i, ll j)
{
ll mi=LLONG_MAX, pj=-1, l=0, r=j, piv, ma, pos=-1;
while(l<=r)
{
piv=(l+r)/2;
ma=calc(piv+pot,j+pot,1);
if(ma>=t[i])
{
l=piv+1;
}
else
{
r=piv-1;
pos=piv;
}
}
pair<ll,ll>ret;
if(pos!=-1)
{
ret=calc2(pos+pot,j+pot,1);
if(mi>ret.fr)
{
mi=ret.fr;
pj=ret.se;
}
}
pos=-1;
l=j;r=m-1;
while(l<=r)
{
piv=(l+r)/2;
ma=calc(piv+pot,j+pot,1);
if(ma>=t[i])
{
l=piv+1;
}
else
{
r=piv-1;
pos=piv;
}
}
if(pos!=-1)
{
ret=calc2(j+pot,pos+pot,1);
if(mi>ret.fr)
{
mi=ret.fr;
pj=ret.se;
}
}
return pj;
}
bool can_reach(int L, int R, int S, int D) {
n=sz(t); m=sz(h);
ll i;
if(S>D)
swap(S,D);
for(i=0; i<n; i++)
{
if(con(i,S,D))
return 1;
if(i+1<n)
{
S=minR(i,S);
D=minR(i,D);
if(S==-1||D==-1)
return 0;
}
}
return 0;
}
