#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) a.begin(), a.end()
struct SparseTable {
int n;
vector<int> lg;
vector<vector<pair<int, int>>> mn;
vector<vector<pair<int, int>>> mx;
SparseTable(vector<int> a) {
n = a.size();
lg.assign(n + 1, 0);
mn.assign(20, vector<pair<int, int>>(n + 1));
mx.assign(20, vector<pair<int, int>>(n + 1));
for (int i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 0; i < n; i++) {
mn[0][i] = mx[0][i] = {a[i], i};
}
for (int h = 1; h < 20; h++) {
for (int i = 0; i + (1 << h) - 1 < n; i++) {
mn[h][i] = min(mn[h - 1][i], mn[h - 1][i + (1 << (h - 1))]);
mx[h][i] = max(mx[h - 1][i], mx[h - 1][i + (1 << (h - 1))]);
}
}
}
int get_min(int l, int r) {
assert(l <= r);
int p = lg[r - l + 1];
return min(mn[p][l], mn[p][r - (1 << p) + 1]).second;
}
int get_max(int l, int r) {
assert(l <= r);
int p = lg[r - l + 1];
return max(mx[p][l], mx[p][r - (1 << p) + 1]).second;
}
};
vector<pair<int, int>> mx;
vector<int> t, sz;
int root(int x) {
if (t[x] == x) return x;
return t[x] = root(t[x]);
}
void join(int a, int b) {
a = root(a);
b = root(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
t[b] = a;
sz[a] += sz[b];
}
void initialize(vector<int> T, vector<int> H) {
int n = T.size();
int m = H.size();
vector<pair<int, int>> segs;
int l = -1, r = -1;
for (int i = 0; i < m; i++) {
if (T[0] > H[i]) {
if (l == -1) {
l = i;
}
r = i;
} else {
if (l != -1) {
segs.push_back({l, r});
}
l = r = -1;
}
}
if (l != -1) segs.push_back({l, r});
SparseTable zt(T), zh(H);
vector<int> far(m);
for (int i = 0; i < m; i++) {
int low = 0, high = n - 1, sol = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (H[i] < T[zt.get_min(0, mid)]) {
sol = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
far[i] = sol;
}
t.resize(m);
sz.resize(m);
for (int i = 0; i < m; i++) {
t[i] = i;
sz[i] = 1;
}
vector<int> lft(m, -1), rgh(m, m);
vector<int> stk;
for (int i = 0; i < m; i++) {
while (!stk.empty() && H[i] <= H[stk.back()]) stk.pop_back();
if (!stk.empty()) lft[i] = stk.back();
stk.push_back(i);
}
stk.clear();
for (int i = m - 1; i >= 0; i--) {
while (!stk.empty() && H[i] <= H[stk.back()]) stk.pop_back();
if (!stk.empty()) rgh[i] = stk.back();
stk.push_back(i);
}
mx.assign(m, {-1, -1});
for (auto [l, r] : segs) {
for (int i = l; i <= r; i++) {
int best = zt.get_max(0, far[i]);
if (lft[i] != -1 && T[best] > H[zh.get_max(lft[i], i)]) {
join(i, lft[i]);
//cout << "CAN REACH " << i << " " << lft[i] << "\n";
}
if (rgh[i] != m && T[best] > H[zh.get_max(i, rgh[i])]) {
//cout << "CAN REACH " << i << " " << rgh[i] << "\n";
join(i, rgh[i]);
}
}
}
}
bool can_reach(int l, int r, int s, int d) {
return root(s) == root(d);
}
