#include <bits/stdc++.h>
using namespace std;
// -------------------- Segment Tree --------------------
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, value}
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; // ✅ fixed
return rleftmost(mid+1, r, s, e, ind*2+2, val);
}
int lefmost(int l, int r, int 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; // ✅ fixed
return rrigtmost(l, mid, s, e, ind*2+1, val);
}
int rigmost(int l, int r, int val){
return rrigtmost(0, n, l, r, 0, val).first;
}
};
// -------------------- Globals --------------------
const int maxm = 2e5+5;
const int lg = 20;
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;
// -------------------- DFS --------------------
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;
}
// -------------------- Initialize --------------------
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]){
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 building
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()){
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});
}
}
// -------------------- LCA --------------------
array<int,2> lca(array<int,2> a, array<int,2> b){
if(a == b){
return {1000000000, -1};
}
int l = -1;
int r = 1e9;
for(int i=lg-1;i>=0;i--){
pair<int,array<int,2>> p = parl[conv(a)][i];
array<int,2> posa = p.second;
if(posa[0] <= b[0] && b[1] <= posa[1]) continue;
l = max(l, p.first);
r = min(r, p.first);
a = posa;
}
for(int i=lg-1;i>=0;i--){
pair<int,array<int,2>> p = parl[conv(b)][i];
array<int,2> posb = p.second;
if(posb[0] <= a[0] && a[1] <= posb[1]) continue;
l = max(l, p.first);
r = min(r, p.first);
b = posb;
}
if(a[0] <= b[0] && b[1] <= a[1]){
l = max(l, parl[conv(b)][0].first);
r = min(r, parr[conv(b)][0].first);
b = parl[conv(b)][0].second;
}
else if(b[0] <= a[0] && a[1] <= b[1]){
swap(a, b);
l = max(l, parl[conv(b)][0].first);
r = min(r, parr[conv(b)][0].first);
b = parl[conv(b)][0].second;
}
else{
l = max(l, parl[conv(b)][0].first);
r = min(r, parr[conv(b)][0].first);
b = parl[conv(b)][0].second;
swap(a, b);
l = max(l, parl[conv(b)][0].first);
r = min(r, parr[conv(b)][0].first);
b = parl[conv(b)][0].second;
}
return {l, r}; // ✅ fixed
}
// -------------------- can_reach --------------------
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 0;
}
array<int,2> arr = lca(rangs, rangd);
if(arr[0] < L || arr[1] > R) return 0;
return 1;
}
