#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
int n,m,lenA,lenB,lenT;
vector<int>t,h,a,b,ter,c;
bool check(vector<int>&v,int&start,int&end){
auto ub=upper_bound(v.begin(),v.end(),start);
return ub==v.end()||*ub>end;
}
void initialize(vector<int>T,vector<int>H){
n=(int)T.size(),m=(int)H.size();
t=T;
for(int i=0;i<m;i++){
h.push_back(H[i]);
if(h[i]>=3)ter.push_back(i);
if(h[i]>=t[0])a.push_back(i);
if(h[i]>=t[n-1])c.push_back(i);
if(!h[i])b.push_back(i);
}
lenA=(int)a.size(),lenB=(int)b.size(),lenT=(int)ter.size();
return;
}
bool can_reach(int l,int r,int s,int d){
if(s>d)swap(s,d);
if(n==1)return check(a,s,d);
if(t==vector<int>{2,1,3}){
int idx=upper_bound(ter.begin(),ter.end(),s)-ter.begin();
if(idx!=lenT&&ter[idx]<d)return 0;
int i1=upper_bound(a.begin(),a.end(),s)-a.begin();
if(i1==lenA||a[i1]>d)return 1;
int i2=lower_bound(b.begin(),b.end(),s)-b.begin();
if(i2!=lenB&&b[i2]<a[i1]||i2-1>=0&&(i1-1<0||b[i2-1]>a[i1-1])){}
else return 0;
int ub=upper_bound(a.begin(),a.end(),d)-a.begin();
int lb=lower_bound(b.begin(),b.end(),d)-b.begin();
if(lb-1>=0&&(ub-1<0||b[lb-1]>a[ub-1]))return 1;
if(lb!=lenB&&(ub==lenA||b[lb]<a[ub]))return 1;
return 0;
}
return check(c,s,d);
}
