#include <bits/stdc++.h>
using namespace std;
const int INF = 1'000'000'000;
const int MAXN = 200'001;
int n; // Number of rows (temperature)
int m; // Number of columns (humidity)
// Prefix sums
// Index i: Min/Max of temperature up to i
// Prefix sum among rows
vector<int> tmin, tmax;
// For each column j, pw(j) contains the maximum temperature
// reachable from column j only going down (without any obstacles)
// so it's reachable from (0,j)
int pw[MAXN];
int h[MAXN];
// lf[i] := First column left of column i having smaller humidity
// If there is no such column lf[i] = i
// Not necessarily directly connected to column i
int lf[MAXN];
// rt[i] := First column right of column i having smaller humidity
int rt[MAXN];
int pl[19][MAXN];
int pr[19][MAXN];
// Building segment tree
// Query O(log(n)), the maximum humidity in range [l,r]
int seg[4*MAXN];
#define LEFT(u) (2*(u)+1)
#define RIGHT(u) (2*(u)+2)
void _build(int u, int l, int r) {
if (l == r) {
seg[u] = h[l];
} else {
int m = (l + r) / 2;
_build(LEFT(u), l, m);
_build(RIGHT(u), m+1, r);
seg[u] = max(seg[LEFT(u)], seg[RIGHT(u)]);
}
}
// sl, sr: Bounds of segment of current node
// l, r: Query bounds
int _query(int u, int l, int r, int sl, int sr) {
if (l > r) {return -INF;}
if (l == sl && r == sr) {return seg[u];}
int sm = (sl + sr) / 2;
return max(
_query(LEFT(u), l, min(r, sm), sl, sm),
_query(RIGHT(u), max(l, sm+1), r, sm+1, sr)
);
}
void build() {_build(0, 0, m-1);}
int query(int l, int r) {
return _query(0, l, r, 0, m-1);
}
void initialize(vector<int> T, vector<int> H) {
n = T.size();
m = H.size();
tmin = T;
tmax = T;
for (int i = 0; i < m; ++i) { h[i] = H[i]; }
for (int i = 1; i < n; ++i) {
tmin[i] = min(T[i], tmin[i-1]);
tmax[i] = max(T[i], tmax[i-1]);
}
// Calculate pw(j)
// pw(j) := For column j, index of row with greatest temperature
// reachable from (0,j)
// Binary search on how far we can go maximally from (0,j)
for (int i = 0; i < m; ++i) {
int l = 0;
int r = n-1;
while (l <= r) {
int mid = (l + r) / 2;
// Cannot reach mid --> at most mid-1
if (tmin[mid] <= H[i]) {
r = mid-1;
} else {
l = mid+1;
}
}
// r contains last index reachable from (0,j)
// In case T[0] <= H[j], r==-1
pw[i] = r == -1 ? -1 : tmax[r];
}
// Build segment tree
build();
stack<int> stk;
for (int i = 0; i < m; ++i) {
lf[i] = i;
while (!stk.empty() && h[stk.top()] >= h[i]) {stk.pop();}
if (!stk.empty()) {lf[i] = stk.top();}
stk.push(i);
}
while (!stk.empty()) {stk.pop();}
for (int i = m-1; i >= 0; --i) {
rt[i] = i;
while (!stk.empty() && h[stk.top()] >= h[i]) {stk.pop();}
if (!stk.empty()) {rt[i] = stk.top();}
stk.push(i);
}
// Binary Lifting
// Base Case: Column with smallest humidity immediatelly left/right
for (int i = 0; i < m; ++i) {
pl[0][i] = pr[0][i] = i;
// Can go left if there exists a column
bool gol = query(lf[i], i) < pw[i] && lf[i] != i;
bool gor = query(i, rt[i]) < pw[i] && rt[i] != i;
if (gor) { pr[0][i] = rt[i]; }
else if (gol) { pr[0][i] = lf[i]; }
if (gol) { pl[0][i] = lf[i]; }
else if (gor) { pl[0][i] = rt[i]; }
}
// Binary Lifting
// i-1 --> i
for (int i = 1; i <= 18; ++i) {
for (int j = 0; j < m; ++j) {
int left = pl[i-1][j];
pl[i][j] = pl[i-1][left];
int right = pr[i-1][j];
pr[i][j] = pr[i-1][right];
}
}
}
bool can_reach(int L, int R, int S, int D) {
if(S > D)swap(S,D);
int s = S,d = D;
for(int i=18;i>=0;i--){
s = pr[i][s];
}
for(int i=18;i>=0;i--){
d = pl[i][d];
}
return query(min(s,D),max(s,D)) < pw[s]
&& query(min(S,d),max(S,d)) < pw[d];
}
