#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
vector<int> T, H;
int N, M;
vector<int> pref_min, pref_max;
vector<int> depth;
vector<vector<int>> st;
vector<int> log2_;
vector<int> parent;
vector<int> sz;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
void init_sparse() {
log2_.resize(M + 1);
for (int i = 2; i <= M; ++i) log2_[i] = log2_[i / 2] + 1;
int K = log2_[M] + 1;
st.assign(K, vector<int>(M));
for (int i = 0; i < M; ++i) st[0][i] = H[i];
for (int k = 1; k < K; ++k) {
int len = 1 << k;
for (int i = 0; i + len <= M; ++i) {
st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
}
int get_max(int l, int r) {
int k = log2_[r - l + 1];
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void initialize(vector<int> _T, vector<int> _H) {
T = _T;
H = _H;
N = T.size();
M = H.size();
// prefix min and max of T
pref_min.resize(N);
pref_max.resize(N);
pref_min[0] = pref_max[0] = T[0];
for (int i = 1; i < N; ++i) {
pref_min[i] = min(pref_min[i - 1], T[i]);
pref_max[i] = max(pref_max[i - 1], T[i]);
}
// depth[j] = first row where prefix_min <= H[j] (or N)
depth.assign(M, N);
vector<pair<int, int>> cols(M);
for (int j = 0; j < M; ++j) cols[j] = {H[j], j};
sort(cols.begin(), cols.end(), greater<pair<int, int>>()); // descending by H
int ptr = 0;
for (int i = 0; i < N; ++i) {
int cur_min = pref_min[i];
while (ptr < M && cols[ptr].first >= cur_min) {
depth[cols[ptr].second] = i;
++ptr;
}
}
// range maximum queries on H
init_sparse();
// DSU initialization
parent.resize(M);
sz.assign(M, 1);
for (int i = 0; i < M; ++i) parent[i] = i;
// process only columns that are free on row 0 (depth > 0)
vector<pair<int, int>> good; // (key, index)
for (int j = 0; j < M; ++j) {
if (depth[j] > 0) {
int L = depth[j] - 1;
int key = pref_max[L];
good.emplace_back(key, j);
}
}
// sort by key descending
sort(good.begin(), good.end(), greater<pair<int, int>>());
set<int> active; // set of indices already processed (good columns)
for (auto& p : good) {
int key = p.first;
int idx = p.second;
auto it = active.lower_bound(idx);
// try to connect with the nearest column on the left
if (it != active.begin()) {
int left = *prev(it);
int mx = get_max(left, idx);
if (mx < key) unite(idx, left);
}
// try to connect with the nearest column on the right
if (it != active.end()) {
int right = *it;
int mx = get_max(idx, right);
if (mx < key) unite(idx, right);
}
active.insert(idx);
}
}
bool can_reach(int L, int R, int S, int D) {
// constraints guarantee L = 0, R = M-1, so the whole grid is available.
return find(S) == find(D);
}
