#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;
//cout<< "\tLEFTMOST : " << mid << " -> " << sl << " : " << mxquery(mid, sl+1) << '\n';
//cout<< "\t\t" << l << ' ' << r << '\n';
if (mxquery(mid, sl) >= val)
l = mid+1;
else {
r = mid;
}
}
ans.first = l;
//cout<< "\tLEFTMOSTEND : " << l << ' ' << mid << ' ' << r << '\n';
l = sr;
r = n-1;
//cout<< '\n';
while (l < r) {
mid = (l+r)/2;
//cout<< "\tRIGHTMOST : " << sr << " -> " << mid << " : " << mxquery(sr, mid+1) << '\n';
//cout<< "\t\t" << l << ' ' << r << '\n';
if (mxquery(sr, mid) >= val)
r = mid;
else {
l = mid+1;
}
}
ans.second = l;
if (h[ans.second] >= val)
ans.second--;
//cout<< "\tRIGHTMOSTEND : " << l << ' ' << mid << ' ' << r << '\n';
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]));
}
/*
cout<< "INC :\n\t";
for (int e : inc)
cout<< e << ' ';
cout<< '\n';
*/
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;
while (l < r) {
mid = (l+r)/2;
if (mx[inc[mid]] <= mn)
r = mid;
else {
lv = mid;
l = mid+1;
r = inc.size();
pair<int, int> rch = tree.open(seg_l, seg_r, T[inc[lv]]);
seg_l = rch.first;
seg_r = rch.second;
}
}
//cout<< seg_l << " -> " << seg_r << "; " << T[inc[lv]] << " :\n";
for (int ind = i; ind <= j; ind++) {
lvl[ind] = inc[lv];
reach[ind].first = seg_l;
reach[ind].second = seg_r;
}
i = j;
}
/*
cout<< "REACH :\n";
for (int i = 0; i < H.size(); i++)
cout<< i << " -> (" << reach[i].first << "; " << reach[i].second << ")\n";
*/
}
bool can_reach(int L, int R, int S, int D) {
if (S == D || reach[S].first == reach[D].first && reach[S].second == reach[D].second)
return true;
return false;
}
