#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>
class SegTree {
public:
int size;
vector<T> t;
function<T(T, T)> f;
T init;
SegTree(){}
SegTree(int n, T init, function<T(T, T)> f, vector<T> &a): init(init), f(f) {
init_tree(n, init, f, a);
}
void initialize(int n, T init_, function<T(T, T)> f_, vector<T> &a) {
init = init_;
f = f_;
size = 1;
while (size < n) size <<= 1;
t.assign(size << 1, init);
build(a, 0, 0, size);
}
void build(vector<T> &a, int pos, int tl, int tr){
if(tr - tl == 1) {
if(tl < a.size()){
t[pos] = a[tl];
}
} else {
int tm = (tr + tl) >> 1;
build(a, 2*pos+1, tl, tm);
build(a, 2*pos+2, tm, tr);
t[pos] = f(t[2*pos+1],t[2*pos+2]);
}
}
void build(vector<T> &a) {
build(a,0,0,size);
}
void update(int i, T val, int pos, int tl, int tr) {
if(tr - tl == 1){
t[pos] = val;
return;
}
int mid = (tl + tr) >> 1;
if(i < mid){
update(i,val,2*pos+1,tl,mid);
} else {
update(i,val,2*pos+2,mid,tr);
}
t[pos] = f(t[2*pos+1],t[2*pos+2]);
}
void update(int i, T x) {
update(i,x,0,0,size);
}
T query(int l, int r, int pos, int tl, int tr) {
if (r <= tl or tr <= l) return init;
if (l <= tl and tr <= r) return t[pos];
int tm = (tl + tr) >> 1;
return f(query(l,r,2*pos+1,tl,tm),query(l,r,2*pos+2,tm,tr));
}
T query(int l, int r) {
return query(l,r,0,0,size);
}
};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
vector<int> T,H;
vector<int> down,lt,rt;
int n,m;
DSU dsu;
SegTree<int> st1, st2;
void initialize(vector<int> t, vector<int> h) {
n = t.size();
m = h.size();
T=t;
H=h;
dsu.init(m);
down.resize(m,0);
lt.resize(m,0);
rt.resize(m,0);
st1.initialize(n,0,[&](int x,int y){
return min(x,y);
},t);
st2.initialize(m,0,[&](int x,int y){
return max(x,y);
},h);
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.query(0, md) > H[i]) {
ans = md;
l = md+1;
} else {
r = md-1;
}
}
down[i] = ans-1;
}
}
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[down[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 = i, r = m;
int ans = i+1;
while (l <= r) {
int md = (l + r) >> 1;
if (st2.query(md, i+1) < T[down[i]]) {
ans = md;
l = md+1;
} else {
r = md-1;
}
}
lt[i] = ans;
}
for(int i = 0; i + 1< n; ++i){
if(down[i] >= 0 and down[i+1] >=0){
dsu.unite(i,i+1);
}
}
for(int i = 0; i < n; ++i){
if(down[i] == -1) continue;
int curr = down[i];
int idx = i;
if(i == n-1)continue;
++i;
bool flag = false;
while(down[i] < curr){
++i;
if(i == rt[i]+1){
flag = true;
break;
}
}
if(flag) continue;
dsu.unite(idx, i);
}
for(int i = n-1; i >= 0; --i){
if(down[i] == -1) continue;
int curr = down[i];
int idx = i;
if(i == 0)continue;
--i;
bool flag = false;
while(down[i] < curr){
--i;
if(i == lt[i]-1){
flag = true;
break;
}
}
if(flag) continue;
dsu.unite(idx, 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);
}
