#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5+4;
const int inf = 1e9+4;
struct Sparce_Table{
int t[N][18];
void build(int n,int a[]){
for (int i=1; i<=n; i++)
t[i][0] = a[i];
for (int j=0; j<17; j++)
for (int i=1; i<=n; i++)
t[i][j+1] = max(t[i][j], t[min(n, i+(1<<j))][j]);
}
int query(int l,int r){
int k = 31 - __builtin_clz(r-l+1);
return max(t[l][k], t[r-(1<<k)+1][k]);
}
} spt;
struct Dsu{
int t[N];
void build(int n){
for (int i=1; i<=n; i++) t[i] = i;
}
int find(int x){
if (x == t[x]) return x;
return t[x] = find(t[x]);
}
void join(int a,int b){
// cout << a << " " << b << "\n";
t[find(a)] = find(b);
}
} dsu;
struct edge{
int a,b,len;
bool operator<(edge x){
return len < x.len;
}
};
int n,m;
int a[N],b[N];
int mx[N],mn[N];
int bL[N],bR[N];
vector<int> adj[N];
int cur,L[N],R[N];
int up[N][18],Max[N][18],Min[N][18];
int h[N];
void dfs(int u,int p){
L[u] = cur++;
up[u][0] = p;
h[u] = h[p] + 1;
Max[u][0] = Min[u][0] = u;
for (int i=1; i<18; i++){
up[u][i] = up[up[u][i-1]][i-1];
Max[u][i] = max(Max[u][i-1], Max[up[u][i-1]][i-1]);
Min[u][i] = min(Min[u][i-1], Min[up[u][i-1]][i-1]);
}
for (int v : adj[u])
if (v != p)
dfs(v, u);
R[u] = cur;
}
bool isa(int a,int b){
return L[a] <= L[b] && R[b] <= R[a];
}
int lca(int a,int b){
if (isa(a, b)) return a;
if (isa(b, a)) return b;
for (int i=17; i>=0; i--)
if (!isa(up[a][i], b))
a = up[a][i];
return up[a][0];
}
int get_max(int u,int k){
int ans = -inf;
for (int i=0; i<18; i++)
if (k>>i&1){
ans = max(ans, Max[u][i]);
u = up[u][i];
}
return ans;
}
int get_min(int u,int k){
int ans = inf;
for (int i=0; i<18; i++)
if (k>>i&1){
ans = min(ans, Min[u][i]);
u = up[u][i];
}
return ans;
}
void initialize(vector<int> T,vector<int> H){
n = T.size(), m = H.size();
mx[0] = -inf, mn[0] = inf;
for (int i=1; i<=n; i++){
a[i] = T[i-1];
mx[i] = max(mx[i-1], a[i]);
mn[i] = min(mn[i-1], a[i]);
}
for (int i=1; i<=m; i++)
b[i] = H[i-1];
b[0] = b[m+1] = -inf;
stack<int> stk;
stk.push(0);
for (int i=1; i<=m; i++){
while (b[stk.top()] > b[i]) stk.pop();
bL[i] = stk.top();
stk.push(i);
}
while (!stk.empty()) stk.pop();
stk.push(m+1);
for (int i=m; i>=1; i--){
while (b[stk.top()] > b[i]) stk.pop();
bR[i] = stk.top();
stk.push(i);
}
spt.build(m, b);
dsu.build(m);
vector<edge> eds;
for (int i=1; i<=m; i++){
if (a[1] <= b[i]) continue;
adj[0].push_back(i);
int l = 1, r = n+1;
while (l+1 < r){
int md = (l+r)>>1;
if (mn[md] > b[i]) l = md;
else r = md;
}
int max_t = mx[l];
int j = bL[i];
if (j != 0 && max_t > spt.query(j, i))
eds.push_back({j, i, i-j});
j = bR[i];
if (j != m+1 && max_t > spt.query(i, j))
eds.push_back({i, j, j-i});
}
sort(eds.begin(), eds.end());
for (auto [a, b, len] : eds){
if (dsu.find(a) == dsu.find(b)) continue;
dsu.join(a, b);
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, 0);
}
bool can_reach(int L, int R, int S, int D) {
L++, R++, S++, D++;
int l = lca(S, D);
int ks = h[S] - h[l] + 1;
int kd = h[D] - h[l] + 1;
int maxi = max(get_max(S, ks), get_max(D, kd));
int mini = min(get_min(S, ks), get_min(D, kd));
return L <= mini && maxi <= R;
}
