#include "obstacles.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,m,temp[maxn],hum[maxn],maxt[maxn],mint[maxn],lpar[20][maxn],rpar[20][maxn],lval[20][maxn],rval[20][maxn],dubl[maxn],dubr[maxn];
struct slog{
int mn,mx;
} st[4*maxn];
slog stspoj(slog a,slog b){
slog r;
if(hum[a.mn]<hum[b.mn])
r.mn=a.mn;
else
r.mn=b.mn;
r.mx=max(a.mx,b.mx);
return r;
}
int stk;
slog get(int lg,int dg,int gde=1,int lc=1,int dc=stk){
if(lg==lc and dg==dc)
return st[gde];
int sred=(lc+dc)/2;
if(dg<=sred)
return get(lg,dg,gde*2,lc,sred);
if(lg>sred)
return get(lg,dg,gde*2+1,sred+1,dc);
slog v1,v2;
v1=get(lg,sred,gde*2,lc,sred);
v2=get(sred+1,dg,gde*2+1,sred+1,dc);
return stspoj(v1,v2);
}
int rod[maxn],vel[maxn];
int getp(int x){
if(rod[x]==x)
return x;
rod[x]=getp(rod[x]);
return rod[x];
}
void spoj(int a,int b){
a=getp(a);
b=getp(b);
if(a==b)
return;
if(vel[a]<vel[b])
swap(a,b);
vel[a]=max(vel[a],vel[b]+1);
rod[b]=a;
return;
}
int najtemp(int x){
int dg=1,gg=n,sred,res;
while(dg<=gg){
sred=(dg+gg)/2;
if(mint[sred]>x){
res=sred;
dg=sred+1;
}
else
gg=sred-1;
}
return maxt[res];
}
void resi(int l,int r,int lp,int rp){
if(r<l)
return;
int m=get(l,r).mn;
// cout<<"RESI "<<m<<" "<<hum[m]<<endl;
// cout<<l<<" "<<r<<" "<<lp<<" "<<rp<<endl;
if(hum[m]>=temp[1])
return;
int mt=najtemp(hum[m]);
bool ml=false,mr=false;
//cout<<mt<<endl;
if(lp!=-1){
int mx=get(lp,m).mx;
// cout<<"LEFT hum "<<mx<<" temp "<<mt<<endl;
if(mx<mt){
spoj(m,lp);
ml=true;
}
}
if(rp!=-1){
int mx=get(m,rp).mx;
// cout<<"RIGHT hum "<<mx<<" temp "<<mt<<endl;
if(mx<mt){
spoj(m,rp);
mr=true;
}
}
if(ml)
lpar[0][m]=lp;
else if(mr)
lpar[0][m]=rp;
if(mr)
rpar[0][m]=rp;
else if(ml)
rpar[0][m]=lp;
resi(l,m-1,lp,m);
resi(m+1,r,m,rp);
}
bool lbio[maxn],rbio[maxn];
vector<int> lstab[maxn],rstab[maxn];
void dfsl(int gde,int d){
if(lbio[gde])
return;
lbio[gde]=true;
dubl[gde]=d;
for(int x:lstab[gde])
dfsl(x,d+1);
}
void dfsr(int gde,int d){
if(rbio[gde])
return;
rbio[gde]=true;
dubr[gde]=d;
for(int x:rstab[gde])
dfsr(x,d+1);
}
int liftl(int x,int d){
int ans=x;
for(int j=18;j>=0;j--){
int ko=lpar[j][x];
if(dubl[ko]>=d){
ans=min(ans,lval[j][x]);
x=ko;
}
}
return ans;
}
int liftr(int x,int d){
int ans=x;
for(int j=18;j>=0;j--){
int ko=rpar[j][x];
if(dubr[ko]>=d){
ans=max(ans,rval[j][x]);
x=ko;
}
}
return ans;
}
vector<int> red;
bool cmp(int a,int b){
return hum[a]<hum[b];
}
void initialize(std::vector<int> T, std::vector<int> H) {
n=T.size();
m=H.size();
for(int i=1;i<=n;i++)
temp[i]=T[i-1];
for(int i=1;i<=m;i++)
hum[i]=H[i-1];
for(int i=1;i<=m;i++)
lpar[0][i]=rpar[0][i]=i;
stk=1;
while(stk<m)
stk<<=1;
for(int i=stk;i<stk+m;i++){
st[i].mx=hum[i-stk+1];
st[i].mn=i-stk+1;
}
for(int i=stk-1;i>=1;i--)
st[i]=stspoj(st[i*2],st[i*2+1]);
for(int i=1;i<=m;i++){
rod[i]=i;
vel[i]=1;
}
maxt[1]=mint[1]=temp[1];
for(int i=2;i<=n;i++){
maxt[i]=max(maxt[i-1],temp[i]);
mint[i]=min(mint[i-1],temp[i]);
}
resi(1,m,-1,-1);
for(int i=1;i<=m;i++){
lstab[lpar[0][i]].push_back(i);
rstab[rpar[0][i]].push_back(i);
}
for(int i=1;i<=m;i++)
red.push_back(i);
sort(red.begin(),red.end(),cmp);
for(int i:red){
dfsl(i,0);
dfsr(i,0);
}
for(int i=0;i<=m;i++){
lval[0][i]=rval[0][i]=i;
}
for(int j=1;j<=18;j++){
for(int i=1;i<=m;i++){
lpar[j][i]=lpar[j-1][lpar[j-1][i]];
lval[j][i]=min(lval[j-1][i],lval[j-1][lpar[j-1][i]]);
rpar[j][i]=rpar[j-1][rpar[j-1][i]];
rval[j][i]=max(rval[j-1][i],rval[j-1][rpar[j-1][i]]);
}
}/*
for(int i=1;i<=m;i++){
cout<<i<<" "<<lpar[0][i]<<endl;
}*/
return;
}
bool can_reach(int L, int R, int S, int D) {
S++;
D++;
if(S>D)
swap(S,D);
if(getp(S)!=getp(D))
return false;
L++;
R++;
int mid=get(S,D).mn;
int l=liftl(S,dubl[mid]);
int r=liftr(D,dubr[mid]);
// cout<<l<<" "<<r<<endl;
return L<=l and r<=R;
}
