#include<bits/stdc++.h>
using namespace std;
#define pb push_back
class seg_tree {
private:
int n;
int tree[800000], mxtree[800000];
vector<int> h;
void build(int u, int l, int r, vector<int> &v) {
if (l > r || r < 0 || l >= n)
return;
if (l == r) {
tree[u] = v[l];
return;
}
int mid = (l+r)/2;
build(2*u, l, mid, v);
build(2*u + 1, mid+1, r, v);
tree[u] = min(tree[2*u], tree[2*u + 1]);
}
void mxbuild(int u, int l, int r, vector<int> &v) {
if (l > r || r < 0 || l >= n)
return;
if (l == r) {
mxtree[u] = v[l];
return;
}
int mid = (l+r)/2;
mxbuild(2*u, l, mid, v);
mxbuild(2*u + 1, mid+1, r, v);
mxtree[u] = max(mxtree[2*u], mxtree[2*u + 1]);
}
int query(int u, int l, int r, int ql, int qr) {
if (r < ql || l > qr)
return (int)(1e9);
if (ql <= l && qr >= r)
return tree[u];
if (l == r)
return (int)(1e9);
int mid = (l+r)/2;
return min(query(2*u, l, mid, ql, qr), query(2*u + 1, mid+1, r, ql, qr));
}
int mxquery(int u, int l, int r, int ql, int qr) {
if (r < ql || l > qr)
return (int)(-1e9);
if (ql <= l && qr >= r)
return mxtree[u];
if (l == r)
return (int)(-1e9);
int mid = (l+r)/2;
return max(mxquery(2*u, l, mid, ql, qr), mxquery(2*u + 1, mid+1, r, ql, qr));
}
public:
void build(vector<int> v) {
n = v.size();
build(1, 0, n-1, v);
mxbuild(1, 0, n-1, v);
h = v;
}
int query(int l, int r) {
return query(1, 0, n-1, l, r);
}
int mxquery(int l, int r) {
return mxquery(1, 0, n-1, l, r);
}
pair<int, int> open(int sl, int sr, int val) {
int l = 0, r = sl, mid;
pair<int, int> ans;
while (l < r) {
mid = (l+r)/2;
if (mxquery(mid, sl) >= val)
l = mid+1;
else
r = mid;
}
ans.first = l;
l = sr;
r = n-1;
while (l < r) {
mid = (l+r)/2;
if (mxquery(sr, mid) >= val)
r = mid;
else {
l = mid+1;
}
}
ans.second = l;
if (h[ans.second] >= val)
ans.second--;
return ans;
}
};
pair<int, int> reach[200000];
int lvl[200000];
vector<int> inc = {0}, mx, t;
seg_tree tree;
void initialize(vector<int> T, vector<int> H) {
int hmx = H[0];
for (int e : H)
hmx = max(hmx, e);
for (int i = 0; i < T.size(); i++)
if (T[i] > hmx)
while (T.size() > i+1)
T.pop_back();
t = T;
tree.build(H);
mx.pb(T[0]);
for (int i = 1; i < T.size(); i++) {
if (T[inc.back()] < T[i]) {
if (!inc.empty() && inc.back()+1 == i)
inc[inc.size()-1] = i;
else
inc.pb(i);
}
mx.pb(min(mx.back(), T[i]));
}
for (int i = 0; i < H.size(); i++) {
if (H[i] >= T[0]) {
reach[i].first = -1;
reach[i].second = -1;
continue;
}
int j = i;
while (j+1 < H.size() && H[j+1] < T[0])
j++;
int seg_l = i, seg_r = j;
int l = 0, r = inc.size(), mid, mn = tree.query(seg_l, seg_r);
int lv = 0;
bool fl = true;
while (l < r) {
mid = (l+r)/2;
if (mx[inc[mid]] <= mn)
r = mid;
else {
lv = mid;
l = mid+1;
}
}
pair<int, int> rch = tree.open(seg_l, seg_r, T[inc[lv]]);
seg_l = rch.first;
seg_r = rch.second;
l = 0, r = inc.size(), lv = 0;
while (l < r) {
mid = (l+r)/2;
if (mx[inc[mid]] <= mn)
r = mid;
else {
lv = mid;
l = mid+1;
}
}
rch = tree.open(seg_l, seg_r, T[inc[lv]]);
seg_l = rch.first;
seg_r = rch.second;
l = 0, r = inc.size(), lv = 0;
while (l < r) {
mid = (l+r)/2;
if (mx[inc[mid]] <= mn)
r = mid;
else {
lv = mid;
l = mid+1;
}
}
rch = tree.open(seg_l, seg_r, T[inc[lv]]);
seg_l = rch.first;
seg_r = rch.second;
for (int ind = i; ind <= j; ind++) {
lvl[ind] = inc[lv];
reach[ind].first = seg_l;
reach[ind].second = seg_r;
}
i = j;
}
}
bool can_reach(int L, int R, int S, int D) {
if (reach[S].first == reach[D].first && reach[S].second == reach[D].second)
return true;
return false;
}
