#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin())
#define sort_uniq(x) sort(all(x)), uniq(x)
#define no_el(x, y) x.find(y) == x.end()
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define sz(x) int(x.size())
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)
#define ld long double
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
const int N = 8e5 + 5;
const int LG = 19;
int n, m;
V<int> t, h;
int stmn[N][LG], stmx[N][LG], lg2[N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int p[N];
V<int> comp[N];
void mrg(int a, int b) {
a = p[a], b = p[b];
if (a == b) return;
if (sz(comp[a]) < sz(comp[b])) swap(a, b);
for (auto i : comp[b]) {
comp[a].pb(i);
p[i] = a;
}
}
void initialize(std::vector<int> T, std::vector<int> H)
{
n = sz(T), m = sz(H);
t.resize(n + 1), h.resize(m + 1);
rep(i, 1, n, 1) t[i] = T[i - 1];
rep(i, 1, m, 1) h[i] = H[i - 1];
rep(i, 1, m, 1) {
stmn[i][0] = h[i];
stmx[i][0] = h[i];
}
rep(j, 1, LG - 1, 1) {
rep(i, 1, m, 1) {
int nx = i + (1 << (j - 1));
if (nx <= m) {
stmn[i][j] = min(stmn[i][j - 1], stmn[nx][j - 1]);
stmx[i][j] = max(stmx[i][j - 1], stmx[nx][j - 1]);
}
else {
stmn[i][j] = stmn[i][j - 1];
stmx[i][j] = stmx[i][j - 1];
}
}
}
lg2[1] = 0;
rep(i, 2, N - 1, 1) {
lg2[i] = lg2[i >> 1] + 1;
}
rep(i, 1, N - 1, 1) {
p[i] = i;
comp[i] = {i};
}
rep(i, 1, n, 1) {
rep(j, 1, m, 1) {
if (t[i] <= h[j]) continue;
rep(it, 0, 3, 1) {
int nxx = i + dx[it];
if (nxx < 1 || nxx > n) continue;
int nxy = j + dy[it];
if (nxy < 1 || nxy > m) continue;
if (t[nxx] > h[nxy]) {
mrg((nxx - 1) * m + nxy, (i - 1) * m + j);
//cout << i << " " << j << " " << nxx << " " << nxy << "\n";
}
}
}
}
}
int min_rng(int l, int r) {
int j = lg2[r - l + 1];
return min(stmn[l][j], stmn[r - (1 << j) + 1][j]);
}
int max_rng(int l, int r) {
int j = lg2[r - l + 1];
return max(stmx[l][j], stmx[r - (1 << j) + 1][j]);
}
bool can_reach1(int l, int r, int s, int d) {
++s; ++d;
if (p[s] == p[d]) return true;
return false;
}
bool can_reach2(int l, int r, int s, int d) {
++s; ++d;
if (s > d) swap(s, d);
//if (max_rng(s, d) < t[1]) return true;
//return false;
l = 1, r = s - 1;
int lb = s, rb = s, ans = s;
rep(i, 1, n, 1) {
int l = 1, r = lb - 1, ans = lb;
while (l <= r) {
int md = l + r >> 1;
if (max_rng(md, s) < t[i]) {
r = md - 1;
ans = md;
}
else l = md + 1;
}
lb = ans;
l = rb + 1, r = m, ans = rb;
while (l <= r) {
int md = l + r >> 1;
if (max_rng(s, md) < t[i]) {
l = md + 1;
ans = md;
}
else r = md - 1;
}
rb = ans;
if (rb >= d) return true;
if (i == n) return false;
if (t[i + 1] <= min_rng(lb, rb)) return false;
}
return false;
}
bool can_reach(int l, int r, int s, int d) {
if (can_reach1(l, r, s, d) != can_reach2(l, r, s, d)) {
rep(i, 1, m, 1) cout << h[i] << endl;
assert(false);
}
return can_reach1(l, r, s, d);
}
