#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;
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]);
}
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);
}
struct Parent {
int par, lcol, rcol;
} pnt[20][MAXN];
void update(int x, int p, int val) {
pnt[0][x].par = p;
auto [a,b] = node[x];
int lb=a,ub=b,mid; while(lb<ub) {
mid=lb+ub>>1;
if(rmq(mid+1,ub) < val) lb=mid+1;
else ub=mid;
} pnt[0][x].rcol = lb;
lb=a,ub=b,mid; while(lb<ub) {
mid=lb+ub>>1;
if(rmq(lb,mid) < val) ub=mid;
else lb=mid+1;
} pnt[0][x].lcol = lb;
}
int 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);
}
}
pi lca(pi a, pi b) {
int r=MAXN, l=-1;
if(dep[a.ff]>dep[b.ff]) swap(a,b);
for(int j=19;j>=0;j--) if(dep[a.ff] <= dep[pnt[j][b.ff].par]) {
if(b.ss==0) r=min(r, pnt[j][b.ff].rcol);
else l=max(l, pnt[j][b.ff].lcol);
b.ff = pnt[j][b.ff].par;
}
if(a.ff==b.ff) return {r,l};
for(int j=19;j>=0;j--) if(pnt[j][a.ff].par^pnt[j][b.ff].par) {
if(a.ss==0) r=min(r, pnt[j][a.ff].rcol);
else l=max(l, pnt[j][a.ff].lcol);
a.ff = pnt[j][a.ff].par;
if(b.ss==0) r=min(r, pnt[j][b.ff].rcol);
else l=max(l, pnt[j][b.ff].lcol);
b.ff = pnt[j][b.ff].par;
}
if(a.ss==0) r=min(r, pnt[0][a.ff].rcol);
else l=max(l, pnt[0][a.ff].lcol);
if(b.ss==0) r=min(r, pnt[0][b.ff].rcol);
else l=max(l, pnt[0][b.ff].lcol);
return {r,l};
}
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;
pnt[0][ncnt] = {0, idx, nx-1};
for(int i=idx;i<nx;i++) num[i] = ncnt;
idx = nx; 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});
pnt[0][ncnt] = {ncnt, a, b};
for(int z:w) {
update(z, ncnt, row[i].ss);
adj[ncnt].push_back(z);
} ncnt++;
}//for(auto x:s2)cout<<x.ff<<bl<<x.ss<<endl;
}//for(int i=0;i<ncnt;i++) cout<<pnt[0][i].par<<bl<<pnt[0][i].lcol<<bl<<pnt[0][i].rcol<<endl;
for(int j=1;j<20;j++) {
for(int i=0;i<ncnt;i++) {
pnt[j][i].par = pnt[j-1][pnt[j-1][i].par].par;
pnt[j][i].rcol = min(pnt[j-1][i].rcol, pnt[j-1][pnt[j-1][i].par].rcol);
pnt[j][i].lcol = max(pnt[j-1][i].lcol, pnt[j-1][pnt[j-1][i].par].lcol);
}
} for(int i=0;i<ncnt;i++) if(pnt[0][i].par==i) {
gcnt++; dfs(i);
}
}
bool can_reach(int L, int R, int S, int D) {
if(S > D) swap(S, D);
int x=num[S], y=num[D];
if(grp[x]^grp[y]) return 0;
auto [a,b] = lca({x,0},{y,1});
return (L<=a && b<=R);
}
