#include <vector>
#include <algorithm>
using namespace std;
const int LOG = 20;
static int n, m;
static vector<int> T_val, H_val;
static vector<int> pt, mt;
static vector<int> W;
static vector<vector<int>> st_W;
static int query_W(int l, int r) {
if (l > r) return -1;
int k = 31 - __builtin_clz(r - l + 1);
return max(st_W[k][l], st_W[k][r - (1 << k) + 1]);
}
static int calc(int h) {
int L = 0, R = n - 1, p = -1;
while (L <= R) {
int mid = L + (R - L) / 2;
if (pt[mid] > h) {
p = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
if (p == -1) return 0;
return mt[p];
}
// Global Kruskal Reconstruction Tree
static vector<int> fa, lc, rc, l_bound, r_bound, rts;
static vector<vector<int>> up_KRT;
static vector<int> depth_KRT;
// Right Expansion Tree
static vector<int> nxt;
static vector<vector<int>> up_R;
static vector<vector<bool>> fail_R;
// Left Expansion Tree
static vector<int> prv;
static vector<vector<int>> up_L;
static vector<vector<bool>> fail_L;
void initialize(vector<int> T, vector<int> H) {
n = T.size(); m = H.size();
T_val = T; H_val = H;
pt.assign(n, 0); mt.assign(n, 0);
pt[0] = T[0]; mt[0] = T[0];
for (int i = 1; i < n; i++) {
pt[i] = min(pt[i - 1], T[i]);
mt[i] = max(mt[i - 1], T[i]);
}
if (m == 1) return;
W.assign(m - 1, 0);
for (int i = 0; i < m - 1; i++) W[i] = max(H[i], H[i + 1]);
st_W.assign(LOG, vector<int>(m - 1, 0));
for (int i = 0; i < m - 1; i++) st_W[0][i] = W[i];
for (int k = 1; k < LOG; k++) {
for (int i = 0; i + (1 << k) <= m - 1; i++) {
st_W[k][i] = max(st_W[k - 1][i], st_W[k - 1][i + (1 << (k - 1))]);
}
}
// Kruskal Reconstruction Tree Setup
struct Edge { int u, v, w, id; bool operator<(const Edge& rhs) const { return w < rhs.w; } };
vector<Edge> edges;
edges.reserve(m - 1);
for (int i = 0; i < m - 1; i++) edges.push_back({i, i + 1, W[i], i});
sort(edges.begin(), edges.end());
vector<int> p(2 * m - 1);
for (int i = 0; i < 2 * m - 1; i++) p[i] = i;
auto find_set = [&](auto& self, int x) -> int { return x == p[x] ? x : p[x] = self(self, p[x]); };
fa.assign(2 * m - 1, -1); lc.assign(2 * m - 1, -1); rc.assign(2 * m - 1, -1);
l_bound.assign(2 * m - 1, 0); r_bound.assign(2 * m - 1, 0);
vector<int> mn_H(2 * m - 1, 0), val(2 * m - 1, 0);
for(int i = 0; i < m; i++) { mn_H[i] = H[i]; l_bound[i] = i; r_bound[i] = i; }
int nxt_node = m;
for (auto e : edges) {
int u = find_set(find_set, e.u), v = find_set(find_set, e.v);
if (u != v) {
fa[u] = fa[v] = nxt_node;
l_bound[nxt_node] = min(l_bound[u], l_bound[v]);
r_bound[nxt_node] = max(r_bound[u], r_bound[v]);
if (l_bound[u] < l_bound[v]) { lc[nxt_node] = u; rc[nxt_node] = v; }
else { lc[nxt_node] = v; rc[nxt_node] = u; }
val[nxt_node] = e.w;
mn_H[nxt_node] = min(mn_H[u], mn_H[v]);
p[u] = p[v] = nxt_node;
nxt_node++;
}
}
vector<bool> flg(2 * m - 1, false);
for (int i = 0; i < 2 * m - 1; i++) {
if (fa[i] != -1 && calc(mn_H[i]) > val[fa[i]]) flg[i] = true;
}
rts.assign(2 * m - 1, 0);
rts[2 * m - 2] = 2 * m - 2;
for (int i = 2 * m - 3; i >= 0; i--) rts[i] = flg[i] ? rts[fa[i]] : i;
up_KRT.assign(2 * m - 1, vector<int>(LOG, -1));
depth_KRT.assign(2 * m - 1, 0);
for (int i = 2 * m - 2; i >= 0; i--) {
if (fa[i] != -1) depth_KRT[i] = depth_KRT[fa[i]] + 1;
up_KRT[i][0] = fa[i] == -1 ? i : fa[i];
}
for (int k = 1; k < LOG; k++) {
for (int i = 0; i < 2 * m - 1; i++) up_KRT[i][k] = up_KRT[up_KRT[i][k - 1]][k - 1];
}
// Build Right Expansion Tree
nxt.assign(m, m);
vector<int> st;
for (int i = 0; i < m; i++) {
while (!st.empty() && H[st.back()] >= H[i]) { nxt[st.back()] = i; st.pop_back(); }
st.push_back(i);
}
up_R.assign(m + 1, vector<int>(LOG, m));
fail_R.assign(m + 1, vector<bool>(LOG, false));
for (int i = 0; i < m; i++) {
up_R[i][0] = nxt[i];
int r_edge = min(m - 2, nxt[i] - 1);
int mx_w = query_W(i, r_edge);
fail_R[i][0] = (calc(H[i]) <= mx_w);
}
for (int k = 1; k < LOG; k++) {
for (int i = 0; i <= m; i++) {
up_R[i][k] = up_R[up_R[i][k - 1]][k - 1];
fail_R[i][k] = fail_R[i][k - 1] | fail_R[up_R[i][k - 1]][k - 1];
}
}
// Build Left Expansion Tree
prv.assign(m, -1);
st.clear();
for (int i = m - 1; i >= 0; i--) {
while (!st.empty() && H[st.back()] >= H[i]) { prv[st.back()] = i; st.pop_back(); }
st.push_back(i);
}
up_L.assign(m + 1, vector<int>(LOG, m)); // FIXED: correctly default array map out-of-bounds to integer 'm' rather than '-1'
fail_L.assign(m + 1, vector<bool>(LOG, false));
for (int i = 0; i < m; i++) {
up_L[i][0] = prv[i] == -1 ? m : prv[i];
int l_edge = prv[i] + 1;
int mx_w = query_W(l_edge, i - 1);
fail_L[i][0] = (calc(H[i]) <= mx_w);
}
for (int k = 1; k < LOG; k++) {
for (int i = 0; i <= m; i++) {
up_L[i][k] = up_L[up_L[i][k - 1]][k - 1];
fail_L[i][k] = fail_L[i][k - 1] | fail_L[up_L[i][k - 1]][k - 1];
}
}
}
bool can_reach(int L, int R, int S, int D) {
if (m == 1) return true;
int rt = rts[S];
int u = S;
for (int k = LOG - 1; k >= 0; k--) {
int p = up_KRT[u][k];
if (depth_KRT[p] >= depth_KRT[rt] && l_bound[p] >= L && r_bound[p] <= R) u = p;
}
if (D >= l_bound[u] && D <= r_bound[u]) return true;
if (u == rt) return false;
int p = fa[u];
if (u == rc[p]) { // Node touches L, expand Right
if (D <= r_bound[u]) return true;
int curr = L;
for (int k = LOG - 1; k >= 0; k--) {
int n_node = up_R[curr][k];
if (n_node != m && n_node <= r_bound[u]) curr = n_node;
}
int x_st = curr;
curr = L;
for (int k = LOG - 1; k >= 0; k--) {
int n_node = up_R[curr][k];
if (n_node != m && n_node <= D - 1) curr = n_node;
}
int x_ed = curr;
if (x_st == x_ed) {
return calc(H_val[x_st]) > query_W(r_bound[u], D - 1);
} else {
if (calc(H_val[x_st]) <= query_W(r_bound[u], nxt[x_st] - 1)) return false;
if (calc(H_val[x_ed]) <= query_W(x_ed, D - 1)) return false;
curr = nxt[x_st];
for (int k = LOG - 1; k >= 0; k--) {
if (up_R[curr][k] != m && up_R[curr][k] <= x_ed) {
if (fail_R[curr][k]) return false;
curr = up_R[curr][k];
}
}
return true;
}
} else { // Node touches R, expand Left
if (D >= l_bound[u]) return true;
int curr = R;
for (int k = LOG - 1; k >= 0; k--) {
int n_node = up_L[curr][k];
if (n_node != m && n_node >= l_bound[u]) curr = n_node;
}
int x_st = curr;
curr = R;
for (int k = LOG - 1; k >= 0; k--) {
int n_node = up_L[curr][k];
if (n_node != m && n_node >= D + 1) curr = n_node;
}
int x_ed = curr;
if (x_st == x_ed) {
return calc(H_val[x_st]) > query_W(D, l_bound[u] - 1);
} else {
if (calc(H_val[x_st]) <= query_W(prv[x_st] + 1, l_bound[u] - 1)) return false;
if (calc(H_val[x_ed]) <= query_W(D, x_ed - 1)) return false;
curr = prv[x_st];
for (int k = LOG - 1; k >= 0; k--) {
if (up_L[curr][k] != m && up_L[curr][k] >= x_ed) {
if (fail_L[curr][k]) return false;
curr = up_L[curr][k];
}
}
return true;
}
}
}
