#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
class DSU {
vector<int> parent, size;
public:
int sets;
DSU(int N = 0) {
init(N);
}
void init(int N){
this->parent.resize(N);
this->size.resize(N, 1);
for(int i = 0; i < N; i++)
this->parent[i] = i;
this->sets = N;
}
int find(int x) {
if(this->parent[x] != x) {
this->parent[x] = find(this->parent[x]);
}
return this->parent[x];
}
void unite(int x, int y) {
int a = find(x);
int b = find(y);
if (a != b) {
if (this->size[a] < this->size[b]) swap(a, b);
this->parent[b] = a;
this->size[a] += this->size[b];
}
}
int get_size(int x) {
return this->size[find(x)];
}
void clear() {
int N = this->parent.size();
for (int i = 0; i < N; i++) {
this->parent[i] = i;
this->size[i] = 1;
}
this->sets = N;
}
};
template <typename T, T (*op)(T, T)>
struct SparseTable {
int N, LOG;
vector<vector<T>> st;
void build(const vector<T> &v) {
N = v.size();
LOG = 32 - __builtin_clz(N);
st.assign(LOG, vector<T>(N));
st[0] = v;
for (int k = 1; k < LOG; k++) {
int len = 1 << k;
int half = len >> 1;
for (int i = 0; i + len <= N; i++) {
st[k][i] = op(st[k-1][i], st[k-1][i+half]);
}
}
}
T query(int l, int r) const {
--r;
int len = r - l + 1;
int k = 31 - __builtin_clz(len);
return op(st[k][l], st[k][r - (1<<k) + 1]);
}
};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
vector<int> T,H;
vector<int> down,lt,rt,downmx;
int n,m;
DSU dsu;
int maxf (int x,int y){
return max(x,y);
};
struct Node {
int idx;
int val;
};
Node nmaxf (Node x, Node y){
Node z;
if(x.val < y.val) swap(x,y);
z.val = x.val;
z.idx = x.idx;
return z;
}
void initialize(vector<int> t, vector<int> h) {
n = t.size();
m = h.size();
T=t;
H=h;
dsu.init(m);
downmx.resize(m,0);
down.resize(m,0);
lt.resize(m,0);
rt.resize(m,0);
static const int INF = 1e9+1;
vector<int> st1(n);
st1[0] = T[0];
for (int i = 1; i < n; ++i)
st1[i] = min(st1[i-1], T[i]);
SparseTable<int,maxf> st2;
st2.build(h);
vector<Node> ret(n);
for(int i = 0; i < n; ++i){
Node qe;
qe.idx = i;
qe.val = T[i];
ret[i] = qe;
}
Node def;
def.idx = 0;
def.val = 0;
// SegTree<Node> st3 = SegTree<Node>(n,def,[&],ret);
SparseTable<Node,nmaxf> st3;
st3.build(ret);
for(int i = 0; i < m; ++i) {
if(t[0] <= h[i]){
down[i] = -1;
}else{
int l = 1, r = n;
int ans = 0;
while (l <= r) {
int md = (l + r) >> 1;
if (st1[md-1] > H[i]) {
ans = md;
l = md+1;
} else {
r = md-1;
}
}
down[i] = ans-1;
downmx[i] = (st3.query(0,ans)).idx;
}
}
for(int i = 0; i < m; ++i){
if(down[i]==-1)continue;
int l = i, r = m;
int ans = i;
while (l <= r) {
int md = (l + r) >> 1;
if (st2.query(i, md) < T[downmx[i]]) {
ans = md;
l = md+1;
} else {
r = md-1;
}
}
rt[i] = ans-1;
}
for(int i = 0; i < m; ++i){
if(down[i]==-1)continue;
int l = 0, r = i;
int ans = i+1;
while (l <= r) {
int md = (l + r) >> 1;
if (st2.query(md, i+1) < T[downmx[i]]) {
ans = md;
r = md-1;
} else {
l = md+1;
}
}
lt[i] = ans;
}
for(int i = 0; i + 1< m; ++i){
if(down[i] >= 0 and down[i+1] >=0){
dsu.unite(i,i+1);
}
}
// SegTree<int> dst(m,0,[&](auto x, auto y){
// return max(x,y);
// },down);
SparseTable<int,maxf> dst;
dst.build(down);
for(int i = 0; i < m; ++i){
if(down[i] == -1) continue;
int curr = downmx[i];
int idx = i;
int l = i+1, r = rt[i];
int ans = i;
while (l <= r) {
int md = (l + r) >> 1;
if (dst.query(i+1, md+1) >= curr) {
ans = md;
r = md-1;
} else {
l = md+1;
}
}
if(ans != i){
dsu.unite(ans,i);
}
}
for(int i = 0; i < m; ++i){
if(down[i] == -1) continue;
int curr = downmx[i];
int idx = i;
int l = lt[i], r = i-1;
int ans = i;
while (l <= r) {
int md = (l + r) >> 1;
if (dst.query(md, i) >= curr) {
ans = md;
l = md+1;
} else {
r = md-1;
}
}
if(ans != i){
dsu.unite(ans,i);
}
}
}
bool can_reach(int L, int R, int S, int D) {
int r1 = dsu.find(S);
int r2 = dsu.find(D);
return (r1==r2);
}
