#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n;
vector<vector<T>> mat;
F func;
SparseTable(const vector<T>& a, const F& f) : func(f) {
n = static_cast<int>(a.size());
int max_log = 32 - __builtin_clz(n);
mat.resize(max_log);
mat[0] = a;
for (int j = 1; j < max_log; j++) {
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int from, int to) const {
assert(0 <= from && from <= to && to <= n - 1);
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
struct edge {
int to;
int val;
edge(){
to = INT_MAX;
val = INT_MIN;
};
edge(int _to, int _val) : to(_to), val(_val) {};
};
void debug_out(edge e) {
debug_out(make_pair(e.to, e.val));
}
void debug_out(vector<edge> e) {
vector<pair<int, int>> ee;
for (auto i : e) ee.push_back({i.to, i.val});
debug_out(ee);
}
int Lg = 18;
vector<vector<edge>> toL;
vector<vector<edge>> toR;
void initialize(std::vector<int> T, std::vector<int> H) {
T.push_back(0);
int n = H.size();
int N = T.size();
vector<int> a(n);
{
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j){return H[i] < H[j];});
int pre = 0;
for (int i : order) {
a[i] = pre;
while (a[i] < N && H[i] >= T[a[i]]) a[i]++;
pre = a[i];
}
}
SparseTable tab_T(T, [&](int i, int j){return min(i, j);});
SparseTable tab_H(H, [&](int i, int j){return min(i, j);});
auto height = [&](int i) {
if (i >= 0 && i < n) return a[i];
return N;
};
auto First_block = [&](int L, int R, int val, int side) {
bool valid = tab_H.get(L, R) < val;
if (!valid) return side == 1 ? -1 : n;
while (R > L) {
int mid = (L + R) / 2;
bool LL = tab_H.get(L, mid) < val;
bool RR = tab_H.get(mid + 1, R) < val;
assert(LL || RR);
if (!LL) L = mid + 1;
else if (!RR) R = mid;
else {
if (side == 1) L = mid + 1;
else R = mid;
}
}
return R;
};
vector<edge> Lpar(n);
vector<edge> Rpar(n);
vector<int> que = {-1};
for (int i = 0; i < n; i++) {
while (que.size() && height(que.back()) <= height(i)) que.pop_back();
if (que.size()) Lpar[i] = edge(que.back(), 0);
que.push_back(i);
}
que = (vector<int>) {n};
for (int i = n - 1; i >= 0; i--) {
while (que.size() && height(que.back()) <= height(i)) que.pop_back();
if (que.size()) Rpar[i] = edge(que.back(), 0);
que.push_back(i);
}
{
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j){return a[i] > a[j];});
for (int i : order) {
int Lp = Lpar[i].to;
if (Lp == INT_MAX) continue;
int Rp = Rpar[i].to;
assert(Rp != INT_MAX);
int val = height(Rp) >= height(Lp) ? -1 : Lpar[Rp].val;
int min_T = tab_T.get(height(i), min(height(Lp), height(Rp)) - 1);
int nxt = First_block(Lp + 1, Rp - 1, min_T, -1);
Lpar[i].val = max(nxt, val);
}
for (int i : order) {
int Rp = Rpar[i].to;
if (Rp == INT_MAX) continue;
int Lp = Lpar[i].to;
assert(Lp != INT_MAX);
int val = height(Lp) >= height(Rp) ? n : Rpar[Lp].val;
int min_T = tab_T.get(height(i), min(height(Lp), height(Rp)) - 1);
int nxt = First_block(Lp + 1, Rp - 1, min_T, +1);
Rpar[i].val = min(nxt, val);
}
}
toL = vector<vector<edge>>(n, vector<edge>(Lg));
toR = vector<vector<edge>>(n, vector<edge>(Lg));
for (int i = 0; i < n; i++) {
toL[i][0] = Lpar[i];
toR[i][0] = Rpar[i];
}
for (int d = 1; d < Lg; d++) {
for (int i = 0; i < n; i++) {
int pL = toL[i][d - 1].to;
int pR = toR[i][d - 1].to;
if (0 <= pL && pL <= n - 1) {
toL[i][d].to = toL[pL][d - 1].to;
toL[i][d].val = max(toL[pL][d - 1].val, toL[i][d - 1].val);
}
if (0 <= pR && pR <= n - 1) {
toR[i][d].to = toR[pR][d - 1].to;
toR[i][d].val = min(toR[pR][d - 1].val, toR[i][d - 1].val);
}
}
}
}
bool can_reach(int L, int R, int S, int D) {
if (S > D) swap(S, D);
if (S == D) return true;
edge curS(S, 200000);
for (int d = 0; d < Lg; d++) {
int np = toR[curS.to][d].to;
if (np == INT_MAX || np >= D) continue;
curS.val = min(curS.val, toR[curS.to][d].val);
curS.to = np;
}
if (curS.val < L) return false;
edge curD(D, -1);
for (int d = 0; d < Lg; d++) {
int np = toL[curD.to][d].to;
if (np == INT_MAX || np <= S) continue;
curD.val = max(curD.val, toL[curD.to][d].val);
curD.to = np;
}
if (curD.val > R) return false;
return true;
}
