#include <bits/stdc++.h>
using namespace std;
//min segTree
struct segTree{
int *st;
int n;
segTree(int siz){
int x = ceil(log2(siz));
x++;
n=siz-1;
st = new int[(1<<x)];
fill(st,st+(1<<x),0);
}
void rupdate(int l, int r, int ind, int i, int val){
if(i<l||i>r){
return;
}
if(l==r){
st[ind]=val;
return;
}
int mid = (l+r)/2;
rupdate(l,mid,ind*2+1,i,val);
rupdate(mid+1,r,ind*2+2,i,val);
st[ind]=min(st[ind*2+1],st[ind*2+2]);
}
void update(int i, int val){
rupdate(0,n,0,i,val);
}
int rquery(int l, int r, int s, int e, int ind){
if(e<l||s>r){
return 1e9;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
return min(rquery(l,mid,s,e,ind*2+1),rquery(mid+1,r,s,e,ind*2+2));
}
int query(int l, int r){
return rquery(0,n,l,r,0);
}
};
const int maxm = 2e5+5;
segTree seg(maxm);
map<array<int,2>,vector<pair<int,array<int,2>>>>g;
map<array<int,2>,vector<pair<int,array<int,2>>>>parl;
map<array<int,2>,vector<pair<int,array<int,2>>>>parr;
set<array<int,2>>rs;
const int lg = 20;
void dfs(pair<int,array<int,2>>node){
array<int,2>st = node.second;
int req = 1e9;
if(g[st].size()){
req=g[st][0].first;
}
if(parl.find(st)!=parl.end()){
return;
}
//create parl and parr
int lo = st[0];
int hi = st[1];
//reql has left most node that can be used to go down
while(lo<hi){
int mid = (lo+hi)/2;
if(seg.query(st[0],mid)<req){
hi=mid;
}
else{
lo=mid+1;
}
}
int reql = lo;
lo = st[0];
hi = st[1];
//reqr has right most node that can be used to go down
while(lo<hi){
int mid = (lo+hi+1)/2;
if(seg.query(mid,st[1])<req){
lo=mid;
}
else{
hi=mid-1;
}
}
int reqr = lo;
parl[st]=vector<pair<int,array<int,2>>>(lg);
parr[st]=vector<pair<int,array<int,2>>>(lg);
if(g[st].size()==0){
//set all to itself
for(int i = 0;i<lg;i++){
parl[st][i]={-1,st};
}
for(int i = 0;i<lg;i++){
parr[st][i]={1e9,st};
}
return;
}
dfs(g[st][0]);
parl[st][0]={reql,g[st][0].second};
parr[st][0]={reqr,g[st][0].second};
for(int i = 1;i<lg;i++){
parl[st][i]={max(parl[st][i-1].first,parl[parl[st][i-1].second][i-1].first),parl[parl[st][i-1].second][i-1].second};
}
for(int i = 1;i<lg;i++){
parr[st][i]={min(parr[st][i-1].first,parr[parr[st][i-1].second][i-1].first),parr[parr[st][i-1].second][i-1].second};
}
if(g[st].size()==0)
return;
assert(g[st].size()==1);
return;
}
void initialize(vector<int> T, vector<int> H) {
int n = T.size();
int m = H.size();
set<array<int,2>>elems;
for(int i = 0;i<m;i++) {
seg.update(i,H[i]);
elems.insert({H[i],i});
}
segTree stt(n);
for(int i = 0;i<n;i++){
stt.update(i,T[i]);
}
//current ranges
set<array<int,2>>rangs;
int las = -1;
for(int i = 0;i<m;i++){
if(T[0]<=H[i]){
//bad
if(las!=-1){
rs.insert({las,i-1});
}
las=-1;
}
else{
if(las==-1)
las=i;
}
}
if(las!=-1){
rs.insert({las,m-1});
}
//graph between ranges
//stores when the range was first found
map<array<int,2>,int>mp;
auto it = elems.begin();
for(int i = 0;i<n;i++){
while(it!=elems.end()&&(*it)[0]<T[i]){
int ind = (*it)[1];
array<int,2>rang = {ind,ind};
bool wor = 0;
int x = 0;
array<int,2>up = {-1,-1};
auto itup = rangs.lower_bound(rang);
if(itup != rangs.end()){
//check if reachable, if yes then nice
up = *itup;
if(up[0]==ind+1){
rang[1]=up[1];
x=stt.query(mp[up],i);
if(x>seg.query(up[0],up[1])){
wor=1;
}
rangs.erase(up);
}
}
rangs.insert(rang);
auto itdow = rangs.lower_bound(rang);
if(itdow != rangs.begin()){
itdow--;
array<int,2>dow = *itdow;
rangs.erase(rang);
if(dow[1]==ind-1){
rang[0]=dow[0];
int f = stt.query(mp[dow],i);
if(f>seg.query(dow[0],dow[1])){
g[dow].push_back({f,rang});
}
rangs.erase(dow);
}
rangs.insert(rang);
}
if(wor){
g[up].push_back({x,rang});
}
it++;
}
}
for(array<int,2>a:rs){
dfs({T[0],a});
}
}
array<int,2> lca(array<int,2>a, array<int,2>b){
if(a==b){
return {1000000000,-1};
}
//must find lca
int l = -1;
int r = 1e9;
//assume lca exists
for(int i = lg-1;i>=0;i--){
array<int,2>posa = parl[a][i].second;
if(posa[0]<=b[0]&&b[1]<=posa[1]){
//posa is ancestor of b
continue;
}
l=max(l,parl[a][i].first);
r=min(r,parr[a][i].first);
a=posa;
}
for(int i = lg-1;i>=0;i--){
array<int,2>posb = parl[b][i].second;
if(posb[0]<=a[0]&&a[1]<=posb[1]){
//posb is ancestor of a
continue;
}
l=max(l,parl[b][i].first);
r=min(r,parr[b][i].first);
b=posb;
}
if((a[0]<=b[0]&&b[1]<=a[1])){
//a is anc of b
l=min(l,parl[b][0].first);
r=min(r,parr[b][0].first);
b=parl[b][0].second;
}
else if(b[0]<=a[0]&&a[1]<=b[1]){
swap(a,b);
l=min(l,parl[b][0].first);
r=min(r,parr[b][0].first);
b=parl[b][0].second;
}
else{
//both must be parented
l=min(l,parl[b][0].first);
r=min(r,parr[b][0].first);
b=parl[b][0].second;
swap(a,b);
l=min(l,parl[b][0].first);
r=min(r,parr[b][0].first);
b=parl[b][0].second;
}
assert(a==b);
return {r,l};
}
bool can_reach(int L, int R, int S, int D) {
if(S>D){
swap(S,D);
}
array<int,2> rangs = *(--rs.upper_bound({S,1000000000}));
array<int,2> rangd = *(--rs.upper_bound({D,1000000000}));
if(parl[rangs][19].second!=parl[rangd][19].second){
return 0;
}
array<int,2>arr = lca(rangs,rangd);
if(arr[0]<L||arr[1]>R){
return 0;
}
return 1;
}
