#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int>k;
vector<int>h;
int x[3][N];
long long n,bati;
void initialize(vector<int> T, vector<int> H) {
n=H.size();
int j=0;
bati=T.size();
for(int j=0; j<H.size(); j++){
if(T[0]<=H[j]){
//x[j]=-1;
k.push_back(j);
}
else{
//x[j]=1;
}
//cout<<x[j]<<" ";
//x[j]=a;
//j++;
}
for(int i=0; i<H.size(); i++){
if(T[bati-1]<=H[i]){
h.push_back(i);
//x[i]=-1;
}
}
if(bati==3){
for(int i=0; i<3; i++){
for(int j=0; j<n; j++){
if(T[i]<=H[j])x[i][j]=-1;
else x[i][j]=1;
}
}
}
return;
}
bool can_reach(int L, int R, int S, int D) {
//L--,R--,S--,D--;
if(S>D)swap(S,D);
if(bati==1){
auto it=lower_bound(k.begin(),k.end(),S);
if(it!=k.end() && *it<D){
return 0;
}
//if(lower_bound(k.begin(),k.end(),S)<D)return 0;
else return true;
}
else if(bati==3){
queue<pair<int,int>>q;
int l[3][n];
for(int i=0; i<3; i++){
for(int j=0; j<n; j++){
l[i][j]=-1;
}
}
q.push({0,S});
l[0][S]=0;
while(q.size()){
pair<int,int>p=q.front();
q.pop();
//x[i+1][j] x[i][j+1] x[i][j-1] x[i-1][j]
if(p.first+1<bati){
if(l[p.first+1][p.second]==-1 && x[p.first+1][p.second]!=-1){
q.push({p.first+1,p.second});
l[p.first+1][p.second]=l[p.first][p.second];
}
}
if(p.first-1>=0){
if(l[p.first-1][p.second]==-1 && x[p.first-1][p.second]!=-1){
q.push({p.first-1,p.second});
l[p.first-1][p.second]=l[p.first][p.second];
}
}
if(p.second+1<n){
if(l[p.first][p.second+1]==-1 && x[p.first][p.second+1]!=-1){
q.push({p.first,p.second+1});
l[p.first][p.second+1]=l[p.first][p.second];
}
}
if(p.second-1>=0){
if(l[p.first][p.second-1]==-1 && x[p.first][p.second-1]!=-1){
q.push({p.first,p.second-1});
l[p.first][p.second-1]=l[p.first][p.second];
}
}
}
if(x[0][D]!=-1){
return true;
}
else return 0;
}
else{
auto it=lower_bound(h.begin(),h.end(),S);
if(it!=h.end() && *it<D){
return 0;
}
//if(lower_bound(k.begin(),k.end(),S)<D)return 0;
else return true;
}
}
