#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);
}
//return index,val
pair<int,int> rleftmost(int l, int r, int s, int e, int ind, int val){
if(e<l||s>r){
return {1e9,1e9};
}
if(st[ind]>val){
return {1e9,1e9};
}
if(l==r){
return {l,st[ind]};
}
int mid = (l+r)/2;
pair<int,int>p = rleftmost(l,mid,s,e,ind*2+1,val);
if(p.second<val){
return p;
}
return rleftmost(mid+1,r,s,e,ind*2+2,val);
}
int lefmost(int l, int r, int val){
//find leftmost index ie l-ans where query<val
return rleftmost(0,n,l,r,0,val).first;
}
pair<int,int> rrigtmost(int l, int r, int s, int e, int ind, int val){
if(e<l||s>r){
return {1e9,1e9};
}
if(st[ind]>val){
return {1e9,1e9};
}
if(l==r){
return {l,st[ind]};
}
int mid = (l+r)/2;
pair<int,int>p = rrigtmost(mid+1,r,s,e,ind*2+2,val);
if(p.second<val){
return p;
}
return rrigtmost(l,mid,s,e,ind*2+1,val);
}
int rigmost(int l, int r, int val){
//find leftmost index ie l-ans where query<val
return rrigtmost(0,n,l,r,0,val).first;
}
};
const int maxm = 2e5+5;
long long conv(array<int,2>a){
return (((long long)a[0])<<20)|a[1];
}
segTree seg(maxm);
unordered_map<long long,vector<pair<int,array<int,2>>>>g;
unordered_map<long long,vector<pair<int,array<int,2>>>>parl;
unordered_map<long long,vector<pair<int,array<int,2>>>>parr;
vector<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[conv(st)].size()){
req=g[conv(st)][0].first;
}
if(parl.find(conv(st))!=parl.end()){
return;
}
int reql = seg.lefmost(st[0],st[1],req);
int reqr = seg.rigmost(st[0],st[1],req);
parl[conv(st)]=vector<pair<int,array<int,2>>>(lg,{-1,st});
parr[conv(st)]=vector<pair<int,array<int,2>>>(lg,{1e9,st});
if(g[conv(st)].size()==0){
return;
}
dfs(g[conv(st)][0]);
array<int,2>las = g[conv(st)][0].second;
vector<pair<int,array<int,2>>>temp(lg);
temp[0]={reql,g[conv(st)][0].second};
for(int i = 1;i<lg;i++){
temp[i]={max(temp[i-1].first,parl[conv(las)][i-1].first),parl[conv(las)][i-1].second};
las=temp[i].second;
}
parl[conv(st)]=temp;
temp[0]={reqr,g[conv(st)][0].second};
las = g[conv(st)][0].second;
for(int i = 1;i<lg;i++){
temp[i]={min(temp[i-1].first,parr[conv(las)][i-1].first),parr[conv(las)][i-1].second};
las=temp[i].second;
}
parr[conv(st)]=temp;
}
void initialize(vector<int> T, vector<int> H) {
int n = T.size();
int m = H.size();
vector<array<int,2>>elems;
for(int i = 0;i<m;i++) {
seg.update(i,H[i]);
elems.push_back({H[i],i});
}
sort(elems.begin(),elems.end());
segTree stt(n);
for(int i = 0;i<n;i++){
stt.update(i,T[i]);
}
//current ranges
int las = -1;
for(int i = 0;i<m;i++){
if(T[0]<=H[i]){
//bad
if(las!=-1){
rs.push_back({las,i-1});
}
las=-1;
}
else{
if(las==-1)
las=i;
}
}
if(las!=-1){
rs.push_back({las,m-1});
}
//graph between ranges
//stores when the range was first found
set<array<int,2>>rangs;
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);
}
}
auto itdow = rangs.lower_bound(rang);
if(itdow != rangs.begin()){
itdow--;
array<int,2>dow = *itdow;
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[conv(dow)].push_back({f,rang});
}
rangs.erase(dow);
}
}
rangs.insert(rang);
if(wor){
g[conv(up)].push_back({x,rang});
}
it++;
}
}
for(array<int,2>a:rs){
dfs({T[0],a});
}
}
struct LCAResult {
array<int,2> range; // actual ancestor range [low,high]
int minReq; // minimum allowed value seen along path
int maxReq; // maximum allowed value seen along path
};
LCAResult lca(array<int,2> a, array<int,2> b) {
if (a == b) {
return {a, -1, (int)1e9}; // trivial case
}
int minReq = -1;
int maxReq = 1e9;
array<int,2> origA = a, origB = b;
// climb a up until it covers b
for (int i = lg-1; i >= 0; i--) {
auto p = parl[conv(a)][i];
auto posa = p.second;
if (!(posa[0] <= b[0] && b[1] <= posa[1])) {
minReq = max(minReq, p.first);
maxReq = min(maxReq, parr[conv(a)][i].first);
a = posa;
}
}
// climb b up until it covers a
for (int i = lg-1; i >= 0; i--) {
auto p = parl[conv(b)][i];
auto posb = p.second;
if (!(posb[0] <= a[0] && a[1] <= posb[1])) {
minReq = max(minReq, p.first);
maxReq = min(maxReq, parr[conv(b)][i].first);
b = posb;
}
}
// now adjust to ensure one is ancestor of the other
if (a[0] <= b[0] && b[1] <= a[1]) {
minReq = max(minReq, parl[conv(b)][0].first);
maxReq = min(maxReq, parr[conv(b)][0].first);
b = parl[conv(b)][0].second;
return {a, minReq, maxReq};
} else if (b[0] <= a[0] && a[1] <= b[1]) {
minReq = max(minReq, parl[conv(a)][0].first);
maxReq = min(maxReq, parr[conv(a)][0].first);
a = parl[conv(a)][0].second;
return {b, minReq, maxReq};
} else {
// both must go one step up
minReq = max(minReq, parl[conv(a)][0].first);
maxReq = min(maxReq, parr[conv(a)][0].first);
a = parl[conv(a)][0].second;
minReq = max(minReq, parl[conv(b)][0].first);
maxReq = min(maxReq, parr[conv(b)][0].first);
b = parl[conv(b)][0].second;
return {a, minReq, maxReq}; // a and b now share parent
}
}
bool can_reach(int L, int R, int S, int D) {
if (S > D) swap(S, D);
array<int,2> rangs = *(upper_bound(rs.begin(), rs.end(), (array<int,2>){S,1000000000}) - 1);
array<int,2> rangd = *(upper_bound(rs.begin(), rs.end(), (array<int,2>){D,1000000000}) - 1);
if (parl[conv(rangs)][lg-1].second != parl[conv(rangd)][lg-1].second) {
return false; // different components
}
LCAResult res = lca(rangs, rangd);
// Check ancestor range lies within [L,R]
if (res.range[0] < L || res.range[1] > R) return false;
// Also check propagated constraints
if (res.minReq < L || res.maxReq > R) return false;
return true;
}
