#pragma GCC optimize("Ofast")
#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cout if(0) cout
#define cerr if(0) cerr
struct SegTree {
v<int> tree;
SegTree() {}
SegTree(int n) {
tree.assign(4*n, 1e9);
}
void build(int p, int l, int r, int i, int x) {
if (l > i || r < i) return;
if (l == r && r == i) {
tree[p] = x;
}
else {
build(2*p, l, (l+r)/2, i, x);
build(2*p+1, (l+r)/2+1, r, i, x);
tree[p] = min(tree[2*p], tree[2*p+1]);
}
}
int query(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 1e9;
if (i <= l && r <= j) return tree[p];
else {
int i1 = query(2*p, l, (l+r)/2, i, j);
int i2 = query(2*p+1, (l+r)/2+1, r, i, j);
return min(i1, i2);
}
}
int find_first(int p, int l, int r, int ql, int x) {
if (r < ql) return 1e9;
if (tree[p] >= x) return 1e9;
if (l == r) return l;
int m = (l+r)/2;
int ans = find_first(2*p, l, m, ql, x);
if (ans == 1e9) {
ans = find_first(2*p+1, m+1, r, ql, x);
}
return ans;
}
int find_last(int p, int l, int r, int qr, int x) {
if (l > qr) return -1e9;
if (tree[p] >= x) return -1e9;
if (l == r) return l;
int m = (l+r)/2;
int ans = find_last(2*p, m+1, r, qr, x);
if (ans == -1e9) {
ans = find_last(2*p+1, l, m, qr, x);
}
return ans;
}
};
struct DSU {
v<int> par;
v<int> L, R;
DSU() {}
DSU(int n) {
par.assign(n, 0);
L.resize(n);
R.resize(n);
rep(i, 0, n) {
par[i] = i;
L[i] = i;
R[i] = i;
}
}
int find(int n) {
return (n == par[n] ? n : par[n] = find(par[n]));
}
void unite(int n1, int n2) {
int p1 = find(n1);
int p2 = find(n2);
par[p1] = p2;
L[p2] = min(L[p1], L[p2]);
R[p2] = max(R[p1], R[p2]);
}
};
struct Tree {
int t;
v<v<int>> lift;
v<v<int>> path;
v<v<pii>> adj;
v<int> h;
int n;
void init(int _n, int _t) {
n = _n;
t = _t;
adj.resize(n);
h.assign(n, -1);
lift.assign(n, v<int>(20, -1));
path.assign(n, v<int>(20, (t ? -1e9 : 1e9)));
}
//Si t es 0 entonces min, si t es 1 max
int join(int x, int y) {
if (t == 1) {
return max(x, y);
}
else return min(x, y);
}
void add(int a, int b, int w) {
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
void dfs(int n, int w, int p=-1, int d=0) {
lift[n][0] = p;
path[n][0] = w;
h[n] = d;
for (auto x : adj[n]) {
if (x.first == p) continue;
int u = x.first;
int ww = x.second;
dfs(x.first, ww, n, d+1);
}
}
void prepare(int r) {
int w = (t ? -1e9 : 1e9);
dfs(r, w);
rep(j, 1, 20) {
rep(i, 0, n) {
if (lift[i][j-1] == -1) continue;
lift[i][j] = lift[lift[i][j-1]][j-1];
path[i][j] = join(path[i][j-1], path[lift[i][j-1]][j-1]);
}
}
}
//h[a] < h[b]
int weight(int a, int b) {
if (h[a] < h[b]) {
swap(a, b);
}
int ans = (t ? -1e9 : 1e9);
int diff = h[a] - h[b];
rep(i, 0, 20) {
if (a == -1) continue;
if ((diff >> i) & 1) {
ans = join(ans, path[a][i]);
a = lift[a][i];
}
}
if (a == b) return ans;
for (int i = 19; i >= 0; i--) {
if (a == -1 || b == -1) continue;
if (lift[a][i] != lift[b][i]) {
ans = join(ans, path[a][i]);
ans = join(ans, path[b][i]);
a = lift[a][i];
b = lift[b][i];
}
}
cerr << a << " "<< b << " " << ans << endl;
if (a != -1) ans = join(ans, path[a][0]);
cerr << a << " "<< b << " " << ans << endl;
if (b != -1) ans = join(ans, path[b][0]);
cerr << a << " "<< b << " " << ans << endl;
cerr << path[a][0] << " " << path[b][0] << endl;
return ans;
}
};
int N, M;
SegTree stT, stH;
v<int> t, h;
v<int> sig;
DSU dsu;
Tree tmn, tmx;
void initialize(std::vector<int> T, std::vector<int> H) {
t = T;
h = H;
N = T.size();
M = H.size();
//rep(i, 0, N) {rep(j, 0, M) {if (T[i] > H[j]) cout << 1 << " ";else cout << 0 << " ";}cout << endl;}
stT = SegTree(N);
stH = SegTree(M);
rep(i, 0, N) {
stT.build(1, 0, N-1, i, T[i]);
}
rep(i, 0, M) {
stH.build(1, 0, M-1, i, H[i]);
}
dsu = DSU(M);
tmn.init(M, 0);
tmx.init(M, 1);
v<int> ord(M);
rep(i, 0, M) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int x, int y) {
return H[x] < H[y];
});
v<int> mnr(M, N);
int pointer = 0;
rep(i, 0, N) {
while (pointer < M && H[ord[pointer]] < T[i]) {
mnr[ord[pointer]] = i;
pointer++;
}
}
v<bool> used(M, false);
for (auto i : ord) {
if (i > 0 && used[i-1]) {
int x = dsu.find(i-1);
int L = dsu.L[x];
int R = dsu.R[x];
int a = mnr[x];
int b = mnr[i];
int val = stT.query(1, 0, N-1, a, b);
if (b == N) val = 0;
int vmn = stH.find_first(1, 0, M-1, L, val);
if (vmn > R) vmn = 1e9;
int vmx = stH.find_last(1, 0, M-1, R, val);
if (vmx < L) vmx = -1e9;
tmx.add(x, i, vmn);
tmn.add(x, i, vmx);
dsu.unite(i, i-1);
}
if (i < M-1 && used[i+1]) {
int x = dsu.find(i+1);
int L = dsu.L[x];
int R = dsu.R[x];
int a = mnr[x];
int b = mnr[i];
int val = stT.query(1, 0, N-1, a, b);
if (b == N) val = 0;
int vmn = stH.find_first(1, 0, M-1, L, val);
if (vmn > R) vmn = 1e9;
int vmx = stH.find_last(1, 0, M-1, R, val);
if (vmx < L) vmx = -1e9;
tmx.add(x, i, vmn);
tmn.add(x, i, vmx);
dsu.unite(i, i+1);
}
used[i] = true;
}
tmn.prepare(ord.back());
tmx.prepare(ord.back());
return;
}
bool can_reach(int L, int R, int s, int d) {
if (tmx.weight(s, d) <= R && tmn.weight(s, d) >= L) return true;
else return false;
}
