//#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ll long long
#define V vector
#define pb push_back
#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);
struct node{
int ind, l, r, t;
};
struct edge{
int to, lft, rgt;
};
const int N = 200000 + 5;
const int M = 16 * N;
const int LG = 19;
const int LG_C = 23;
int n, m;
V<int> t, h;
int stmn[N][LG], stmx[N][LG];
int tmn[N][LG], tmx[N][LG];
int lg2[N];
int p[M], sz_[M];
V<edge> adj[M];
int up[M][LG_C], upl[M][LG_C], upr[M][LG_C];
bool dad[M];
int dep[M];
int nd[N];
int timer = 1;
map<tuple<int,int,int>, int> mp;
void crt(int x){
if (x >= M) assert(false);
p[x] = x;
sz_[x] = 1;
dad[x] = true;
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
int min_rng(int l, int r){
int j = lg2[r - l + 1];
return min(stmn[l][j], stmn[r - (1 << j) + 1][j]);
}
int max_rng(int l, int r){
int j = lg2[r - l + 1];
return max(stmx[l][j], stmx[r - (1 << j) + 1][j]);
}
int mnt_rng(int l, int r){
int j = lg2[r - l + 1];
return min(tmn[l][j], tmn[r - (1 << j) + 1][j]);
}
int mxt_rng(int l, int r){
int j = lg2[r - l + 1];
return max(tmx[l][j], tmx[r - (1 << j) + 1][j]);
}
void make_edge(node x, node y){
dad[x.ind] = false;
int mn = mnt_rng(x.t, y.t);
int l = x.l, r = x.r - 1, ans = x.r;
while (l <= r) {
int md = (l + r) >> 1;
if (min_rng(x.l, md) < mn) ans = md, r = md - 1;
else l = md + 1;
}
int nl = ans;
l = x.l + 1; r = x.r; ans = x.l;
while (l <= r) {
int md = (l + r) >> 1;
if (min_rng(md, x.r) < mn) ans = md, l = md + 1;
else r = md - 1;
}
int nr = ans;
adj[y.ind].pb({x.ind, nl, nr});
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return;
if(sz_[a] < sz_[b]) swap(a, b);
p[b] = a;
sz_[a] += sz_[b];
}
void expand(node x){
if(x.l == 1 && x.r == m) return;
if(x.t == n) return;
int vl = min(h[x.l - 1], h[x.r + 1]);
if(mxt_rng(x.t + 1, n) <= vl) return;
int l = x.t + 1, r = n - 1, ans = n;
while(l <= r){
int md = (l + r) >> 1;
if(mxt_rng(x.t + 1, md) <= vl) l = md + 1;
else ans = md, r = md - 1;
}
if(mnt_rng(x.t + 1, ans) <= min_rng(x.l, x.r)) return;
int nwt = ans;
l = 1; r = x.l - 1; ans = x.l;
while(l <= r){
int md = (l + r) >> 1;
if(max_rng(md, x.l) < t[nwt]) ans = md, r = md - 1;
else l = md + 1;
}
int nwl = ans;
l = x.r + 1; r = m; ans = x.r;
while(l <= r){
int md = (l + r) >> 1;
if(max_rng(x.r, md) < t[nwt]) ans = md, l = md + 1;
else r = md - 1;
}
int nwr = ans;
auto key = make_tuple(nwl, nwr, nwt);
if(mp.count(key)){
make_edge(x, {mp[key], nwl, nwr, nwt});
}else{
mp[key] = timer;
crt(timer);
make_edge(x, {timer, nwl, nwr, nwt});
++timer;
expand({timer - 1, nwl, nwr, nwt});
}
}
void dfs(int v){
for (auto e : adj[v]) {
int ch = e.to;
dep[ch] = dep[v] + 1;
up[ch][0] = v;
upl[ch][0] = e.lft;
upr[ch][0] = e.rgt;
for (int i = 1; i < LG_C; ++i) {
up[ch][i] = up[up[ch][i - 1]][i - 1];
upl[ch][i] = max(upl[ch][i - 1], upl[up[ch][i - 1]][i - 1]);
upr[ch][i] = min(upr[ch][i - 1], upr[up[ch][i - 1]][i - 1]);
}
dfs(ch);
}
}
void tr(int root){
for (int i = 0; i < LG_C; ++i) {
up[root][i] = root;
upl[root][i] = 0;
upr[root][i] = m + 1;
}
dep[root] = 0;
dfs(root);
}
bool is_s(int a, int b, int l, int r){
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b];
for (int i = 0; i < LG_C; ++i)
if (d & (1 << i)) {
if (upl[a][i] > r || upr[a][i] < l) return false;
a = up[a][i];
}
if (a == b) return true;
for (int i = LG_C - 1; i >= 0; --i) {
if (up[a][i] != up[b][i]) {
if (upl[a][i] > r || upr[a][i] < l) return false;
if (upl[b][i] > r || upr[b][i] < l) return false;
a = up[a][i];
b = up[b][i];
}
}
if (upl[a][0] > r || upr[a][0] < l) return false;
if (upl[b][0] > r || upr[b][0] < l) return false;
return true;
}
void initialize(V<int> T, V<int> H){
n = T.size();
m = H.size();
t.assign(n + 1, 0);
h.assign(m + 2, 1e9 + 7);
for(int i = 1; i <= n; i++) t[i] = T[i - 1];
for(int i = 1; i <= m; i++) h[i] = H[i - 1];
lg2[1] = 0;
for(int i = 2; i < N; i++) lg2[i] = lg2[i >> 1] + 1;
for(int i = 1; i <= m; i++) stmn[i][0] = stmx[i][0] = h[i];
for(int j = 1; j < LG; j++)
for(int i = 1; i + (1 << (j - 1)) <= m; i++){
stmn[i][j] = min(stmn[i][j - 1], stmn[i + (1 << (j - 1))][j - 1]);
stmx[i][j] = max(stmx[i][j - 1], stmx[i + (1 << (j - 1))][j - 1]);
}
for(int i = 1; i <= n; i++) tmn[i][0] = tmx[i][0] = t[i];
for(int j = 1; j < LG; j++)
for(int i = 1; i + (1 << (j - 1)) <= n; i++){
tmn[i][j] = min(tmn[i][j - 1], tmn[i + (1 << (j - 1))][j - 1]);
tmx[i][j] = max(tmx[i][j - 1], tmx[i + (1 << (j - 1))][j - 1]);
}
int ls = 1;
bool las = false;
for(int i = 1; i <= m + 1; i++){
if(t[1] > h[i]){
nd[i] = timer;
las = true;
}else{
if(las){
crt(timer);
++timer;
expand({timer - 1, ls, i - 1, 1});
}
las = false;
ls = i + 1;
}
}
for (int i = 1; i < timer; ++i) {
for (auto e : adj[i]) {
merge(i, e.to);
//cout << i << " " << e.to << "\n";
}
}
for(int i = 1; i < timer; i++)
if(dad[i]) tr(i);
//cout << nd[2] << " " << nd[6] << endl;
}
bool can_reach(int l, int r, int s, int d){
++l; ++r; ++s; ++d;
if (find(nd[s]) != find(nd[d])) return false;
return is_s(nd[s], nd[d], l, r);
}
