#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;
const int MAXM=2e5+1;
vector<ll> segH, IH, DH, comp[MAXM], miT, maT;
vector<pair<ll,ll>>seg2H;
ll potT = 1, potH = 1, n, m, id[MAXM];
ll INF = LLONG_MAX;
vector<int>t,h;
ll calc(ll a, ll b, ll nod)
{
if(IH[nod]>b||DH[nod]<a)
return 0;
if(IH[nod]>=a&&DH[nod]<=b)
return segH[nod];
return max(calc(a,b,nod*2),calc(a,b,nod*2+1));
}
pair<ll,ll> calcMi(ll a, ll b, ll nod)
{
if(IH[nod]>b||DH[nod]<a)
return {INF,0};
if(IH[nod]>=a&&DH[nod]<=b)
return seg2H[nod];
pair<ll,ll>p1=calcMi(a,b,nod*2),p2=calcMi(a,b,nod*2+1);
if(p1.fr<p2.fr)
return p1;
return p2;
}
void unionfind(ll x, ll y)
{
ll a=id[x], b=id[y];
if(a==b)
return;
if(sz(comp[a])<sz(comp[b]))
swap(a,b);
for(auto k:comp[b])
{
comp[a].pb(k);
id[k]=a;
}
}
void cons(ll x)
{
if(t[0]<=h[x])
return;
ll l=0, r=n-1, piv, pos=0;
while(l<=r)
{
piv=(l+r)/2;
if(miT[piv]>h[x])
{
l=piv+1;
pos=piv;
}
else
r=piv-1;
}
ll ma=maT[pos];
l=0, r=x;
pos=x;
while(l<=r)
{
piv=(l+r)/2;
if(calc(piv+potH, x+potH,1)>=ma)
{
l=piv+1;
}
else
{
r=piv-1;
pos=piv;
}
}
l=x, r=m-1;
ll pos2=x;
while(l<=r)
{
piv=(l+r)/2;
if(calc(x+potH, piv+potH,1)>=ma)
{
r=piv-1;
}
else
{
l=piv+1;
pos2=piv;
}
}
pair<ll,ll>p=calcMi(pos+potH,pos2+potH,1);
unionfind(p.se,x);
}
void initialize(std::vector<int> T, std::vector<int> H)
{
t=T;
h=H;
n = sz(T);
miT.resize(n);
maT.resize(n);
miT[0]=T[0];
maT[0]=T[0];
for(ll i=1; i<n; i++)
{
miT[i]=min(miT[i-1],1ll*T[i]);
maT[i]=max(maT[i-1],1ll*T[i]);
}
m = sz(H);
ll i;
while (potH < m)
potH *= 2;
segH.resize(potH*2, INF);
seg2H.resize(potH*2,{INF,0});
IH.resize(potH * 2);
DH.resize(potH * 2);
for (i = potH; i < potH * 2; i++)
IH[i] = DH[i] = i;
for (i = 0; i < m; i++)
{
seg2H[i+potH]={H[i],i};
segH[i + potH] = H[i];
}
for (i = potH - 1; i > 0; i--)
{
IH[i] = IH[i * 2];
DH[i] = DH[i * 2 + 1];
segH[i]=max(segH[i*2],segH[i*2+1]);
seg2H[i]=seg2H[i*2];
if(seg2H[i].fr>seg2H[i*2+1].fr)
seg2H[i]=seg2H[i*2+1];
}
for(i=0; i<m; i++)
{
comp[i]={i};
id[i]=i;
}
for(i=0; i<m; i++)
cons(i);
return;
}
bool can_reach(int L, int R, int S, int D)
{
return id[S]==id[D];
}
