#include<bits/stdc++.h>
using namespace std;
const int mxN = 200000;
#define pb push_back
class seg_tree {
private:
int n;
vector<int> tree, maxtree;
void minbuild(int u, int l, int r, vector<int> &V) {
if (r < 0 || l >= n || l > r)
return;
if (l == r) {
tree[u] = V[l];
return;
}
int mid = (l+r)/2;
minbuild(2*u, l, mid, V);
minbuild(2*u + 1, mid+1, r, V);
tree[u] = min(tree[2*u], tree[2*u + 1]);
}
void maxbuild(int u, int l, int r, vector<int> &V) {
if (r < 0 || l >= n || l > r)
return;
if (l == r) {
maxtree[u] = V[l];
return;
}
int mid = (l+r)/2;
maxbuild(2*u, l, mid, V);
maxbuild(2*u + 1, mid+1, r, V);
maxtree[u] = max(maxtree[2*u], maxtree[2*u + 1]);
}
int minquery(int u, int l, int r, int il, int ir) {
if (r < 0 || l >= n || l > r)
return INT_MAX;
if (il <= l && ir >= r)
return tree[u];
if (l == r)
return INT_MAX;
int mid = (l+r)/2;
return min(minquery(2*u, l, mid, il, ir), minquery(2*u + 1, mid+1, r, il, ir));
}
int maxquery(int u, int l, int r, int il, int ir) {
if (r < 0 || l >= n || l > r)
return 0;
if (il <= l && ir >= r)
return maxtree[u];
if (l == r)
return 0;
int mid = (l+r)/2;
return max(maxquery(2*u, l, mid, il, ir), maxquery(2*u + 1, mid+1, r, il, ir));
}
public:
void build(vector<int> &T) {
n = T.size();
tree.resize(4*n, 1e9);
minbuild(1, 0, n-1, T);
//for (int i = 0; i < 4*n; i++)
// cout<< tree[i] << ' ';
//cout<< '\n';
}
void buildmx(vector<int> &T) {
maxtree.resize(4*n, -1);
maxbuild(1, 0, n-1, T);
}
pair<int, int> open(int t, int seg_l, int seg_r) {
int l = seg_r, r = n-1, mid;
while (l < r) {
mid = (l+r)/2;
if (maxquery(1, 0, n-1, seg_r, mid) >= t)
r = mid;
else
l = mid+1;
}
seg_r = l;
l = 0, r = seg_l;
while (l < r) {
mid = (l+r)/2;
if (maxquery(1, 0, n-1, mid, seg_l) >= t)
l = mid+1;
else
r = mid;
}
seg_l = l;
return make_pair(seg_l, seg_r);
}
int query(int l, int r) {
return minquery(1, 0, n-1, l, r);
}
};
vector<int> rg, lf;
void initialize(vector<int> T, vector<int> H){
seg_tree hseg, tseg;
tseg.build(T);
hseg.build(H);
hseg.buildmx(H);
vector<int> inc;
inc.pb(0);
for (int i = 1; i < T.size(); i++)
if (T[inc.back()] < T[i])
inc.pb(i);
rg.resize(H.size()); lf.resize(H.size());
for (int i = 0; i < H.size(); i++) {
if (T[0] <= H[i])
continue;
int j = i;
while (j+1 < H.size() && T[0] > H[j+1])
j++;
int seg_l = i, seg_r = j;
//cout<< i << ":\n";
int l = 1, r = inc.size(), mid, lst = 0;
while (l < r) {
mid = (l+r)/2;
//cout<< '\t' << l << ' ' << mid << ' ' << r << '\n';
if (tseg.query(inc[lst], inc[mid]) <= hseg.query(seg_l, seg_r))
r = mid;
else {
//cout<< "\there\n";
lst = l;
l = mid+1;
r = inc.size();
pair<int, int> opn = hseg.open(T[inc[mid]], seg_l, seg_r);
seg_l = opn.first;
seg_r = opn.second;
}
}
/*
for (int ind = 1; ind < inc.size(); ind++) {
if (tseg.query(inc[ind-1], inc[ind]) <= hseg.query(seg_l, seg_r))
break;
while (seg_l-1 >= 0 && H[seg_l-1] < T[inc[ind]])
seg_l--;
while (seg_r+1 < H.size() && H[seg_r+1] < T[inc[ind]])
seg_r++;
//cout<< '\t' << ind << " -> (" << seg_l << "; " << seg_r << ")\n";
//cout<< "\t\t" << tseg.query(inc[ind-1], inc[ind]) << ' ' << hseg.query(seg_l, seg_r) << '\n';
}
*/
for (int ind = i; ind <= j; ind++) {
rg[ind] = seg_r;
lf[ind] = seg_l;
}
i = j;
}
/*
cout<< "(LF; RG)\n";
for (int i = 0; i < H.size(); i++)
cout<< i << " -> (" << lf[i] << "; " << rg[i] << ")\n";
*/
return;
}
bool can_reach(int L, int R, int S, int D){
return (rg[S] == rg[D] && lf[S] == lf[D]);
}
