#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) {
int 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) {
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) {
int p = lg[r - l + 1];
return max(mx[p][l], mx[p][r - (1 << p) + 1]).second;
}
};
vector<pair<int, int>> mx;
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 {
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;
}
auto get = [&](int l, int c) -> pair<int, int> {
int low = 0, high = c, sol1 = c;
while (low <= high) {
int mid = (low + high) / 2;
if (H[zh.get_max(mid, c)] < T[l]) {
sol1 = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
low = c;
high = m - 1;
int sol2 = c;
while (low <= high) {
int mid = (low + high) / 2;
if (H[zh.get_max(c, mid)] < T[l]) {
sol2 = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return {sol1, sol2};
};
mx.assign(m, {-1, -1});
for (auto [l, r] : segs) {
int p = zh.get_min(l, r);
int best = zt.get_max(0, far[p]);
pair<int, int> inter = get(best, p);
for (int i = l; i <= r; i++) {
mx[i] = inter;
}
}
}
bool can_reach(int l, int r, int s, int d) {
if (mx[s].second < mx[d].first || mx[s].first > mx[d].second) return false;
return true;
}
