#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 200005, LOG = 17;
struct DSU {
int uf[mxN];
void init() { memset(uf, -1, sizeof(uf)); }
int find(const int i) { return uf[i] < 0 ? i : uf[i] = find(uf[i]); }
bool unite(int a, int b) {
if ((a = find(a)) == (b = find(b)))
return false;
if (uf[a] > uf[b])
swap(a, b);
uf[a] += uf[b];
uf[b] = a;
return true;
}
} uf;
struct ST {
int st[mxN][LOG+1];
void init(const vt<int> &A) {
const int N = size(A);
FOR(i, 0, N-1)
st[i][0] = A[i];
FOR(j, 1, LOG)
FOR(i, 0, N-(1<<j))
st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
}
int query(const int l, const int r) {
const int n = 31 - __builtin_clz(r-l+1);
return max(st[l][n], st[r-(1<<n)+1][n]);
}
} st;
int N, M;
void initialize(const vt<int> T, const vt<int> H) {
N = size(T), M = size(H);
vt<int> pmin = T, pmax = T;
FOR(i, 1, N-1) {
pmin[i] = min(pmin[i-1], T[i]);
pmax[i] = max(pmax[i-1], T[i]);
}
vt<vt<int>> rem(N+1);
FOR(i, 0, M-1) {
int lo = 0, hi = N;
while (lo < hi) {
const int mid = lo + hi >> 1;
if (pmin[mid] > H[i])
lo = mid + 1;
else
hi = mid;
}
rem[lo].push_back(i);
}
vt<vt<int>> join(N+1);
st.init(H);
FOR(i, 0, M-2) {
int lo = 0, hi = N;
while (lo < hi) {
const int mid = lo + hi >> 1;
if (pmax[mid] > max(H[i], H[i+1]))
hi = mid;
else
lo = mid + 1;
}
join[lo].push_back(i);
}
set<int> active;
FOR(i, 0, M-1)
active.insert(i);
uf.init();
FOR(x, 0, N-1) {
for (const auto &i : rem[x])
if (active.count(i))
active.erase(active.find(i));
for (const auto &i : join[x]) {
const auto it = active.upper_bound(i);
if (it == active.end() || it == active.begin())
continue;
const int j = *prev(it), k = *it;
if (T[x] > st.query(j, k)) {
uf.unite(j, k);
active.erase(active.find(H[j] < H[k] ? k : j));
}
}
}
}
bool can_reach(int L, int R, int S, int D) {
return uf.find(S) == uf.find(D);
}
