#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) (lower_bound(all(v), (x))-(v).begin())
#define ubd(v,x) (upper_bound(all(v), (x))-(v).begin())
#define sz(v) ((int)(v).size())
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*2;
const ll MOD = 998244353;
const ll INF = 1e18;
vector<pi> row;
vector<int> lpar, rpar;
set<pi> s1, s2;
pi node[MAXN]; int ncnt;
pi info[MAXN];
map<pi, int> mp;
int num[MAXN];
int grp[MAXN], gcnt;
int root(int x, vector<int>& par) {
return par[x]==x?x:par[x]=root(par[x], par);
}
int par[20][MAXN], dep[MAXN];
vector<int> adj[MAXN];
void dfs(int here) {
grp[here] = gcnt;
for(int there:adj[here]) {
dep[there] = dep[here]+1;
dfs(there);
}
}
int lca(int a, int b) {
if(dep[a]>dep[b]) swap(a,b);
for(int j=19;j>=0;j--) if(dep[a] <= dep[par[j][b]]) {
b = par[j][b];
}
if(a==b) return a;
for(int j=19;j>=0;j--) if(par[j][a]^par[j][b]) {
a=par[j][a], b=par[j][b];
} return par[0][a];
}
int sp[20][MAXN];
int rmq(int a, int b) {
int h = (int)floor(log2(b-a+1));
return min(sp[h][a], sp[h][b-(1<<h)+1]);
}
void initialize(std::vector<int> T, std::vector<int> H) {
int n = T.size(), m = H.size();
for(int i=0;i<m;i++) sp[0][i] = H[i];
for(int j=1;j<20;j++) for(int i=0;i<m;i++) {
sp[j][i] = sp[j-1][i];
if(i+(1<<(j-1)) < m) sp[j][i] = min(sp[j][i], sp[j-1][i+(1<<(j-1))]);
}
row.push_back({0,0});
for(int i=1;i<n;i++) {
if(T[row.back().ff] < T[i])
row.push_back({i,0});
}
for(int i=1;i<sz(row);i++) {
int mn = INT_MAX;
for(int j=row[i-1].ff+1;j<row[i].ff;j++) {
mn = min(mn, T[j]);
} row[i].ss = mn;
}
lpar.resize(m); rpar.resize(m);
for(int i=0;i<m;i++) lpar[i]=rpar[i]=i;
int idx=0;
while(idx<m) {
while(idx<m && H[idx]>=T[0]) idx++;
if(idx==m) break;
int nx=idx;
while(nx<m && H[nx]<T[0]) nx++;
rpar[idx] = nx-1; lpar[nx-1] = idx;
node[ncnt] = {idx,nx-1};
mp[node[ncnt]] = ncnt;
int mn=rmq(idx, nx-1);
s1.insert({mn, ncnt});
info[ncnt].ff = mn;
mn = INT_MAX;
if(idx-1>=0) mn=min(mn,H[idx-1]);
if(nx<m) mn=min(mn, H[nx]);
s2.insert({mn, ncnt});
info[ncnt].ss = mn;
for(int i=idx;i<nx;i++) num[i] = ncnt;
idx = nx; par[0][ncnt] = ncnt; ncnt++;
}
auto clean = [&] (int x) {
s1.erase({info[x].ff, x}); s2.erase({info[x].ss, x}); mp.erase(node[x]);
};
for(int i=1;i<sz(row);i++) {
while(s1.size() && s1.rbegin()->ff >= row[i].ss) {
auto x = s1.rbegin()->ss;
clean(x);
}
while(s2.size() && s2.begin()->ff < T[row[i].ff]) {
auto x = s2.begin()->ss; auto [a,b] = node[x];
clean(x);
vector<int> w = {x};
while(a-1>=0) {
if(H[a-1] >= T[row[i].ff]) break;
int a1 = root(a-1, lpar);
if(mp.find({a1,a-1}) != mp.end()) {
w.push_back(mp[{a1,a-1}]);
clean(mp[{a1,a-1}]);
}
a = a1;
} while(b+1<m) {
if(H[b+1] >= T[row[i].ff]) break;
int b1 = root(b+1, rpar);
if(mp.find({b+1,b1}) != mp.end()) {
w.push_back(mp[{b+1,b1}]);
clean(mp[{b+1,b1}]);
}
b = b1;
}//for(int x:w)cout<<x<<bl;cout<<endl;
rpar[a] = b; lpar[b] = a; node[ncnt] = {a,b}; mp[node[ncnt]] = ncnt;
info[ncnt] = {rmq(a,b), min((a-1>=0?H[a-1]:INT_MAX), (b+1<m?H[b+1]:INT_MAX))};
s1.insert({info[ncnt].ff, ncnt}); s2.insert({info[ncnt].ss, ncnt});
par[0][ncnt] = ncnt;
for(int z:w) {
par[0][z] = ncnt;
adj[ncnt].push_back(z);
} ncnt++;
}//for(auto x:s2)cout<<x.ff<<bl<<x.ss<<endl;
}
for(int j=1;j<20;j++) {
for(int i=0;i<ncnt;i++) par[j][i] = par[j-1][par[j-1][i]];
} for(int i=0;i<ncnt;i++) if(par[0][i]==i) {
gcnt++; dfs(i);
}
}
bool can_reach(int L, int R, int S, int D) {
int x=num[S], y=num[D];
return grp[x]==grp[y];
}
