#include<bits/stdc++.h>
using namespace std;
const int mxN = 200000;
#define pb push_back
class seg_tree {
private:
int n;
vector<int> tree;
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]);
}
int query(int u, int l, int r, int ql, int qr) {
if (l > r || r < 0 || l >= n)
return INT_MAX;
if (ql <= l && qr >= r)
return tree[u];
if (l == r)
return INT_MAX;
int mid = (l+r)/2;
return min(query(2*u, l, mid, ql, qr), query(2*u + 1, mid+1, r, ql, qr));
}
public:
void build(vector<int> &v) {
n = v.size();
tree.resize(4*n);
build(1, 0, n, v);
}
int query(int l, int r) {
return query(1, 0, n, l, r);
}
};
vector<pair<int, int>> reach;
vector<int> inc = {0}, mx, lvl, t;
seg_tree tree;
void initialize(vector<int> T, vector<int> H) {
t = T;
tree.build(H);
reach.resize(H.size());
lvl.resize(H.size());
mx.pb(T[0]);
for (int i = 1; i < T.size(); i++) {
if (T[inc.back()] < T[i])
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;
//cout<< seg_l << " -> " << seg_r << " :\n";
while (l < r) {
mid = (l+r)/2;
//cout<< '\t' << l << ' ' << mid << ' ' << r << '\n';
if (mx[inc[mid]] <= mn)
r = mid;
else {
lv = mid;
l = mid+1;
}
}
//cout<< "\tRESULT : " << lv << '\n';
while (seg_l-1 >= 0 && T[inc[lv]] > H[seg_l-1])
seg_l--;
while (seg_r+1 < H.size() && T[inc[lv]] > H[seg_r+1])
seg_r++;
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<< '\t' << i << " -> (" << reach[i].first << "; " << reach[i].second << ")\n";
}
*/
}
bool can_reach(int L, int R, int S, int D) {
int lv = max(lvl[S], lvl[D]);
int l = max(reach[S].first, reach[D].first);
int r = min(reach[S].second, reach[D].second);
if (l > r)
return false;
int mn = tree.query(l, r);
return (mn < t[lv]);
}
