#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];
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]);
//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);
}
if(rp!=-1){
int mx=get(m,rp).mx;
// cout<<"RIGHT hum "<<mx<<" temp "<<mt<<endl;
if(mx<mt)
spoj(m,rp);
}
resi(l,m-1,lp,m);
resi(m+1,r,m,rp);
}
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];
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);
return;
}
bool can_reach(int L, int R, int S, int D) {
return getp(S+1)==getp(D+1);
}
