#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h;
vector<int> parent;
struct DSU{
vector<int> e;
vector<int> z;
DSU(int n){
for(int i=0;i<n;i++){
e.push_back(-1);
z.push_back(i);
}
}
int parent(int i){
if(e[i]<0){
return i;
}
e[i] = parent(e[i]);
return e[i];
}
bool join(int i,int j){
int x = parent(i);
int y = parent(j);
if(x==y){
return false;
}
if(e[x]<e[y]){
swap(x,y);
}
e[y] += e[x];
e[x] = y;
if(h[z[x]]<h[z[y]]){
z[y] = z[x];
}
return true;
}
};
DSU ans(0);
struct SegmentTree{
vector<int> l;
int n;
SegmentTree(int m){
n = m;
for(int i=0;i<2*n;i++){
l.push_back(0);
}
}
void update(int i,int x){
i += n;
l[i] = x;
while(i>0){
i /= 2;
l[i] = min(l[2*i],l[2*i+1]);
}
}
int query(int i,int j){
i += n;
j += n;
int ans = l[i];
while(i<j){
if(i&2){
ans = min(l[i],ans);
i++;
}
if(j&2){
ans = min(l[j-1],ans);
j--;
}
i /= 2;
j /= 2;
}
return ans;
}
};
void initialize(vector<int> T, vector<int> H){
int n = T.size();
int m = H.size();
vector<int> t1 = {T[0]};
vector<pair<int,int>> l;
for(int i=1;i<n;i++){
t1.push_back(min(t1[i-1],T[i]));
}
for(int i=0;i<m;i++){
h.push_back(H[i]);
}
for(int i=0;i<n;i++){
l.push_back({T[i],-i-1});
}
for(int i=0;i<m;i++){
l.push_back({H[i],i});
}
sort(l.begin(),l.end());
vector<int> stop(m);
int cur = n;
for(int i=0;i<n+m;i++){
if(l[i].second<0){
cur = min(cur,-l[i].second-1);
}
else{
stop[l[i].second] = cur;
}
}
vector<pair<int,int>> l1;
for(int i=0;i<m;i++){
l1.push_back({stop[i],i});
}
for(int i=0;i<n;i++){
l1.push_back({i,-i-1});
}
sort(l1.begin(),l1.end());
cur = -1;
vector<int> start(m);
for(int i=0;i<n+m;i++){
if(l1[i].second<0){
cur = max(cur,0);
int x = -l1[i].second-1;
if(T[x]>T[cur]){
cur = x;
}
}
else{
start[l1[i].second] = cur;
}
}
vector<pair<int,int>> l2;
for(int i=0;i<m;i++){
l2.push_back({H[i],i});
}
for(int i=0;i<n;i++){
l2.push_back({T[i],-i-1});
}
sort(l2.begin(),l2.end());
vector<int> first(m);
cur = n;
for(int i=n+m-1;i>=0;i--){
if(l2[i].second<0){
cur = min(cur,-l2[i].second-1);
}
else{
first[l2[i].second] = cur;
}
}
vector<pair<int,int>> s1;
for(int i=0;i<m-1;i++){
int x;
if(H[i]>H[i+1]){
x = i;
}
else{
x = i+1;
}
s1.push_back({first[x],-i-1});
}
for(int i=0;i<m;i++){
s1.push_back({start[i],i});
}
sort(s1.begin(),s1.end());
DSU dsu(m);
for(int i=0;i<m;i++){
ans.e.push_back(-1);
ans.z.push_back(i);
}
for(int i=0;i<m;i++){
parent.push_back(-1);
}
for(int i=0;i<2*m-1;i++){
if(s1[i].second<0){
dsu.join(-s1[i].second,-s1[i].second-1);
}
else{
if(s1[i].second!=dsu.z[dsu.parent(s1[i].second)]){
parent[s1[i].second] = dsu.z[dsu.parent(s1[i].second)];
ans.join(s1[i].second,dsu.z[dsu.parent(s1[i].second)]);
}
}
}
}
bool can_reach(int L, int R, int S, int D){
return ans.parent(S)==ans.parent(D);
}
