#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 200005, LOG = 17;
struct ST {
int st[mxN][LOG+1];
void init(const vt<int> &A) {
const int N = size(A);
FOR(i, 0, N-1)
st[i][0] = A[i];
FOR(j, 1, LOG)
FOR(i, 0, N-(1<<j))
st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
}
int query(const int l, const int r) {
const int n = 31 - __builtin_clz(r-l+1);
return max(st[l][n], st[r-(1<<n)+1][n]);
}
} st;
int N, M, pmin[mxN], pmax[mxN];
vt<int> T, H;
ari2 lift_left[mxN][LOG+1], lift_right[mxN][LOG+1];
bool check(const int i, const int j) {
if (j < 0)
return false;
int lo = 0, hi = N;
while (lo < hi) {
const int mid = lo + hi >> 1;
if (pmax[mid] > st.query(min(i, j), max(i, j)))
hi = mid;
else
lo = mid + 1;
}
return lo < N && pmin[lo] > H[i];
};
void initialize(const vt<int> _T, const vt<int> _H) {
T = _T, H = _H;
N = size(T), M = size(H);
pmin[0] = pmax[0] = T[0];
FOR(i, 1, N-1) {
pmin[i] = min(pmin[i-1], T[i]);
pmax[i] = max(pmax[i-1], T[i]);
}
vt<int> L(M), R(M), stk;
FOR(i, 0, M-1) {
while (size(stk) && H[stk.back()] >= H[i])
stk.pop_back();
L[i] = size(stk) ? stk.back() : -1;
stk.push_back(i);
}
stk.clear();
ROF(i, M-1, 0) {
while (size(stk) && H[stk.back()] >= H[i])
stk.pop_back();
R[i] = size(stk) ? stk.back() : -1;
stk.push_back(i);
}
st.init(H);
vt<int> ord(M);
iota(all(ord), 0);
sort(all(ord), [&](const int &a, const int &b) { return H[a] < H[b]; });
for (const auto &i : ord) {
lift_left[i][0] = {check(i, L[i]) ? L[i] : i, i};
lift_right[i][0] = {check(i, R[i]) ? R[i] : i, i};
if (check(i, L[i]))
lift_right[i][0] = max(lift_right[i][0], lift_right[L[i]][0]);
if (check(i, R[i]))
lift_left[i][0] = min(lift_left[i][0], lift_left[R[i]][0]);
}
FOR(j, 1, LOG)
FOR(i, 0, M-1) {
lift_left[i][j][0] = lift_left[lift_left[i][j-1][0]][j-1][0];
lift_left[i][j][1] = max(lift_left[i][j-1][1], lift_left[lift_left[i][j-1][0]][j-1][1]);
lift_right[i][j][0] = lift_right[lift_right[i][j-1][0]][j-1][0];
lift_right[i][j][1] = min(lift_right[i][j-1][1], lift_right[lift_right[i][j-1][0]][j-1][1]);
}
}
bool can_reach(int L, int R, int S, int D) {
const auto good = [&](const int x) { return L <= x && x <= R; };
const auto el = [&](int i) {
ROF(j, LOG, 0)
if (good(lift_left[i][j][0]) && good(lift_left[i][j][1]))
i = lift_left[i][j][0];
return i;
};
const auto er = [&](int i) {
ROF(j, LOG, 0)
if (good(lift_right[i][j][0]) && good(lift_right[i][j][1]))
i = lift_right[i][j][0];
return i;
};
vt<int> a = {el(S), er(S)}, b = {el(D), er(D)};
for (const auto &i : a)
for (const auto &j : b)
if (check(i, j) && check(j, i))
return true;
return false;
}
