#include "obstacles.h"
#include <bits/stdc++.h>
#define ll long long
#define inf 1e17
#define dbg(x) cerr<<#x<< ' '<<x<<endl;
using namespace std;
vector<ll> t;
vector<ll> h;
vector<ll> par;
vector<ll> sz;
vector<ll> maxt;
vector<ll> mint;
vector<vector<ll>> sp;
int lg[200001];
ll findrep(ll node)
{
if(par[node]==node)
{
return node;
}
return par[node]=findrep(par[node]);
}
void unionsets(ll u, ll v)
{
u=findrep(u);
v=findrep(v);
if(u==v)
{
return;
}
if(sz[u] < sz[v]) swap(u,v);
par[v]=u;
sz[u]+=sz[v];
}
ll n,m;
bool free(ll x, ll y)
{
return t[y] > h[x];
}
ll maxh(ll l, ll r)
{
ll sze=lg[r-l+1];
return max(sp[l][sze],sp[r-sze+1][sze]);
}
ll akbarT(ll c)
{
ll l=0;
ll r=n-1;
ll ab3ad=0;
while(l<=r)
{
ll mid=(l+r)/2;
if(mint[mid]>h[c])
{
ab3ad=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
return maxt[ab3ad];
}
void initialize(std::vector<int> T, std::vector<int> H) {
t.assign(T.begin(), T.end());
h.assign(H.begin(), H.end());
n = t.size();
m = h.size();
par.resize(m);
maxt.resize(n);
mint.resize(n);
sz.resize(m);
sp.assign(m,vector<ll>(18));
lg[1]=0;
for (int i=2;i<=200000;i++)
{
lg[i]=lg[i/2]+1;
}
for (int i=0;i<m;i++)
{
par[i]=i;
sz[i]=1;
}
for (int i=0;i<n;i++)
{
if(i==0)
{
maxt[i]=mint[i]=t[i];
}
else
{
maxt[i]=max(maxt[i-1],t[i]);
mint[i]=min(mint[i-1],t[i]);
}
}
for (int j=0;j<=17;j++)
{
for (int i=0;i+(1<<j)<=m;i++)
{
if(j==0)
{
sp[i][j]=h[i];
}
else
{
sp[i][j]=max(sp[i][j-1],sp[i+(1<<j)][j-1]);
}
}
}
stack<pair<ll,ll>> st;
for (int i=0;i<n;i++)
{
while(st.size() && st.top().first > h[i])
{
st.pop();
}
if(!st.empty())
{
ll nxt=st.top().second;
ll kbir=akbarT(i);
if(kbir > maxh(nxt,i))
{
unionsets(i,nxt);
}
}
st.push({h[i],i});
}
while(st.size()) st.pop();
for (int i=n-1;i>=0;i--)
{
while(st.size() && st.top().first > h[i])
{
st.pop();
}
if(!st.empty())
{
ll nxt=st.top().second;
ll kbir=akbarT(i);
if(kbir > maxh(i,nxt))
{
unionsets(i,nxt);
}
}
st.push({h[i],i});
}
return;
}
bool can_reach(int L, int R, int S, int D) {
return findrep(S)==findrep(D);
}
