#include "obstacles.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 2 * 1e5 + 15;
int n, m, mx[maxN], mn[maxN], lft[maxN], rgt[maxN], st[maxN][20], lg[maxN], par[maxN], sz[maxN];
int query(int l, int r) {
if (r > l) return 0;
int z = lg[r - l + 1];
return max(st[l][z], st[r - (1 << z) + 1][z]);
}
void make_set() {
for (int i = 1; i <= m; i++) {
par[i] = i; sz[i] = 1;
}
}
int find_set(int x) {
if (par[x] == x)
return x;
return par[x] = find_set(par[x]);
}
void union_set(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
}
void initialize(vector<int> t, vector<int> h) {
n = t.size(); m = h.size();
t.insert(t.begin(), 0);
h.insert(h.begin(), 0);
mx[0] = -inf; mn[0] = inf;
for (int i = 1; i <= n; i++) {
mx[i] = max(mx[i - 1], t[i]);
mn[i] = min(mn[i - 1], t[i]);
}
stack<int> s;
for (int i = 1; i <= m; i++) {
while (!s.empty() && h[s.top()] > h[i]) s.pop();
if (s.empty()) lft[i] = 0;
else lft[i] = s.top();
s.push(i);
}
while (!s.empty()) lft[s.top()] = 0, s.pop();
for (int i = m; i >= 1; i--) {
while (!s.empty() && h[s.top()] > h[i]) s.pop();
if (s.empty()) rgt[i] = m + 1;
else rgt[i] = s.top();
s.push(i);
}
while (!s.empty()) rgt[s.top()] = m + 1, s.pop();
for (int i = 2; i <= m; i++)
lg[i] = lg[i / 2] + 1;
for (int i = 1; i <= m; i++)
st[i][0] = h[i];
for (int j = 1; j < 20; j++)
for (int i = 1; i + (1 << j) - 1 <= m; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
make_set();
for (int i = 1; i <= m; i++) {
if (mn[1] <= h[i]) continue;
int l = 1, r = n, mid, ans;
while (l <= r) {
mid = (l + r) / 2;
if (mn[mid] > h[i]) {
ans = mid; l = mid + 1;
} else r = mid - 1;
}
if (lft[i] != 0 && mx[ans] > query(lft[i], i)) union_set(lft[i], i);
if (rgt[i] != m + 1 && mx[ans] > query(i, rgt[i])) union_set(i, rgt[i]);
}
}
bool can_reach(int L, int R, int S, int D) {
return (find_set(S + 1) == find_set(D + 1));
}
// int main() {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> T(N), H(M);
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%d", &T[i]));
// for (int i = 0; i < M; i++)
// assert(1 == scanf("%d", &H[i]));
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> L(Q), R(Q), S(Q), D(Q);
// for (int i = 0; i < Q; i++)
// assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i]));
// fclose(stdin);
// std::vector<bool> A(Q);
// initialize(T, H);
// for (int i = 0; i < Q; i++)
// A[i] = can_reach(L[i], R[i], S[i], D[i]);
// for (int i = 0; i < Q; i++)
// if (A[i])
// printf("1\n");
// else
// printf("0\n");
// fclose(stdout);
// return 0;
// }
