#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
#define mk(a,b) make_pair(a,b)
vector<int> par,w;
int find(int ind){
if(par[ind]==ind)return ind;
return par[ind]=find(par[ind]);
}
void join(int u,int v){
u=find(u),v=find(v);
if(u==v)return;
if(w[u]<w[v])swap(u,v);
par[v]=u;
w[u]+=w[v];
}
int maRange(int l,int r, vector<vector<int>>&ma){
int t=log2(r-l+1);
int ans=ma[l][t];
ans=max(ans,ma[r+1-(1<<t)][t]);
return ans;
}
void initialize(vector<int> T, vector<int> H) {
int m=H.size(),n=T.size();
par.clear();
par.resize(m);
w.resize(m);
for(int i=0;i<H.size();i++){
par[i]=i;
w[i]=1;
}
vector<int> maxT(n);
maxT[0]=T[0];
for(int i=1;i<n;i++){
maxT[i]=max(maxT[i-1],T[i]);
}
vector<int> nH(m,-1),pH(m,-1);
vector<int> q;
for(int i=m-1;i>=0;i--){
while(q.size()&&H[i]<H[q.back()]){
q.pop_back();
}
if(q.size()) nH[i]=q.back();
q.push_back(i);
}
q.clear();
for(int i=0;i<m;i++){
while(q.size()&&H[i]<H[q.back()]){
q.pop_back();
}
if(q.size()) pH[i]=q.back();
q.push_back(i);
}
vector<vector<int>> ma(m,vector<int>(20,1e9+1));
for(int i=0;i<m;i++) ma[i][0]=H[i];
for(int i=m-1;i>=0;i--){
for(int j=0;j<19;j++){
int nxt=i+(1<<j);
if(nxt<m)ma[i][j+1]=max(ma[i][j],ma[nxt][j]);
else break;
}
}
vector<pair<int,int>> s;
for(int i=0;i<m;i++){
s.push_back(mk(H[i],i));
}
sort(s.rbegin(),s.rend());
vector<int> rw(m,-1);
int cur=-1;
for(auto &x:s){
while(cur<m-1 && x.first<T[cur+1])cur++;
if(cur==-1)rw[x.second]=cur;
else rw[x.second]=maxT[cur];
x.first=rw[x.second];
}
for(auto x:s){
//check right
int ind=x.second,val=x.first;
if(nH[ind]!=-1){
int nex=nH[ind];
if(rw[ind]>maRange(ind,nex,ma)){
join(ind,nex);
}
}
//check left
if(pH[ind]!=-1){
int nex=pH[ind];
if(rw[ind]>maRange(nex,ind,ma)){
join(ind,nex);
}
}
}
}
bool can_reach(int L, int R, int S, int D) {
return find(S)==find(D);
}
