#include "obstacles.h"
#include "bits/stdc++.h"
#define pb push_back
#define fs first
#define sc second
using namespace std;
int const N = 2e5 + 10, LG = 19;
int rec[N];
bool dead[N], done[N];
int par[N];
int mn[N];
vector<int> ch[N];
struct segtree{
int n;
vector<int> t;
void build(vector<int> &a) {
n = a.size();
t.assign(2 * n, 0);
for (int i = 0; i < n; i++) t[i + n] = a[i];
for (int i = n - 1; i > 0; i--) t[i] = max(t[i << 1], t[i << 1 | 1]);
}
int get(int l, int r) {
l += n; r += n;
int res = 0;
while (l <= r) {
if (l & 1) res = max(res, t[l++]);
if (!(r & 1)) res = max(res, t[r--]);
l >>= 1; r >>= 1;
}
return res;
}
};
segtree mh, mt;
int root(int n){
if(par[n] == n) return n;
else return root(par[n]);
}
set<pair<int,int>> S;
void unite(int u, int v){
u = root(u);
v = root(v);
if (u == v) return;
ch[u].pb(v);
S.erase({mn[u], u});
S.erase({mn[v], v});
par[v] = u;
mn[u] = min(mn[u], mn[v]);
S.insert({mn[u], u});
}
vector<int> t, h;
void rem(int u, int k){
vector<int> f;
f.pb(u);
for (int i = 0; i < f.size(); i++) {
for (auto j : ch[f[i]]) {
if (!done[j]) f.pb(j);
}
}
for (auto i : f) {
done[i] = 1;
rec[i] = min(rec[i], k);
}
}
void initialize(vector<int> T, vector<int> H){
t = T;
h = H;
int n = t.size(), m = h.size();
mh.build(h);
mt.build(t);
vector<pair<int,int>> vls;
for (int i = 0; i < m; i++) {
rec[i] = n - 1;
dead[i] = 1;
vls.pb({h[i], i});
par[i] = i;
mn[i] = h[i];
ch[i] = {};
}
sort(vls.rbegin(), vls.rend());
for (int i = 0; i < n; i++) {
while (!vls.empty() and t[i] > vls.back().fs) {
int ind = vls.back().sc;
vls.pop_back();
dead[ind] = 0;
S.insert({mn[ind], ind});
if (ind + 1 < m and !dead[ind + 1]) unite(ind, ind + 1);
if (ind - 1 >= 0 and !dead[ind - 1]) unite(ind, ind - 1);
}
while (!S.empty() and (*rbegin(S)).fs >= t[i]) {
int z = (*rbegin(S)).sc;
rem(z, i - 1);
S.erase(*rbegin(S));
}
}
}
bool can_reach(int L, int R, int S, int D){
if (D < S) swap(D, S);
int z = mh.get(S, D);
int h = min(rec[S], rec[D]);
int g = mt.get(0, h);
if (g > z) return 1;
return false;
}
