#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
struct Mnt {
vector<vector<int>> table;
void init (int n, vector<int> v) {
table.clear();
table.resize(32-__builtin_clz(n));
table[0] = v;
for (size_t i = 1; i < table.size(); i++) for (int j = 0; j <= n-(1<<i); j++)
table[i].push_back(min(table[i-1][j], table[i-1][j+(1<<i-1)]));
}
int query (int l, int r) {
int x = 31-__builtin_clz(r-l);
return min(table[x][l], table[x][r-(1<<x)]);
}
};
struct Mxt {
vector<vector<int>> table;
void init (int n, vector<int> v) {
table.clear();
table.resize(32-__builtin_clz(n));
table[0] = v;
for (size_t i = 1; i < table.size(); i++) for (int j = 0; j <= n-(1<<i); j++)
table[i].push_back(max(table[i-1][j], table[i-1][j+(1<<i-1)]));
}
int query (int l, int r) {
int x = 31-__builtin_clz(r-l);
return max(table[x][l], table[x][r-(1<<x)]);
}
};
vector<Mnt> bl;
vector<Mxt> br;
int n, m;
vector<int> t, h;
Mxt mxt;
Mnt mnt;
void initialize (vector<int> T, vector<int> H) {
t = T;
h = H;
n = t.size();
m = h.size();
mxt.init(m, h);
mnt.init(n, t);
vector<vector<pair<int, int>>> blift;
blift.resize(20, vector<pair<int, int>>(m));
bl.resize(20);
br.resize(20);
Mxt bruh;
bruh.init(n, t);
for (int i = 0; i < m; i++) {
int down = 0;
for (int j = 20; j--;) if (down+(1<<j) <= n && mnt.query(0, down+(1<<j)) > h[i])
down += 1<<j;
blift[0][i] = {i, i+1};
if (down) {
for (int j = 20; j--;) {
if (blift[0][i].f-(1<<j) >= 0 && mxt.query(blift[0][i].f-(1<<j), i) < bruh.query(0, down))
blift[0][i].f -= 1<<j;
if (blift[0][i].s+(1<<j) <= m && mxt.query(i, blift[0][i].s+(1<<j)) < bruh.query(0, down))
blift[0][i].s += 1<<j;
}
}
}
for (int i = 1; i < 20; i++) {
vector<int> a, b;
for (auto j: blift[i-1]) {
a.push_back(j.f);
b.push_back(j.s);
}
bl[i-1].init(m, a);
br[i-1].init(m, b);
for (int j = 0; j < m; j++) {
blift[i][j].f = bl[i-1].query(blift[i-1][j].f, blift[i-1][j].s);
blift[i][j].s = br[i-1].query(blift[i-1][j].f, blift[i-1][j].s);
}
}
vector<int> a, b;
for (auto j: blift.back()) {
a.push_back(j.f);
b.push_back(j.s);
}
bl.back().init(m, a);
br.back().init(m, b);
}
bool can_reach (int l, int r, int a, int b) {
if (h[a] >= t[0] || h[b] >= t[0]) return 0;
r++;
int la, ra, lb, rb;
{
int x = a, y = a+1;
for (int i = 20; i--;) {
if (bl[i].query(x, y) >= l && br[i].query(x, y) <= r) {
int c = bl[i].query(x, y);
y = br[i].query(x, y);
x = c;
}
}
x = max(l, bl[0].query(x, y));
y = min(r, br[0].query(x, y));
x = max(l, bl[0].query(x, y));
y = min(r, br[0].query(x, y));
x = max(l, bl[0].query(x, y));
y = min(r, br[0].query(x, y));
x = max(l, bl[0].query(x, y));
la = x;
ra = y;
}
{
int x = b, y = b+1;
for (int i = 20; i--;) {
if (bl[i].query(x, y) >= l && br[i].query(x, y) <= r) {
int c = bl[i].query(x, y);
y = br[i].query(x, y);
x = c;
}
}
x = max(l, bl[0].query(x, y));
y = min(r, br[0].query(x, y));
x = max(l, bl[0].query(x, y));
y = min(r, br[0].query(x, y));
x = max(l, bl[0].query(x, y));
y = min(r, br[0].query(x, y));
x = max(l, bl[0].query(x, y));
lb = x;
rb = y;
}
return la == lb && ra == rb;
}
