#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
struct SparseTable
{
int sparse[200005][20];
void init(vector<int> a)
{
int n = a.size();
for(int i = 0; i < n; i++) sparse[i][0] = a[i];
for(int j = 1; j <= 18; j++){
for(int i = 0; i < n; i++){
sparse[i][j] = sparse[i][j-1];
int p = i + (1 << (j-1));
if(p < n) sparse[i][j] = max(sparse[i][j], sparse[p][j-1]);
}
}
}
int query(int l, int r)
{
int x = __lg(r-l+1);
return max(sparse[l][x], sparse[r-(1<<x)+1][x]);
}
};
struct SparseTableMin
{
int sparse[200005][20];
void init(vector<int> a)
{
int n = a.size();
for(int i = 0; i < n; i++) sparse[i][0] = a[i];
for(int j = 1; j <= 18; j++){
for(int i = 0; i < n; i++){
sparse[i][j] = sparse[i][j-1];
int p = i + (1 << (j-1));
if(p < n) sparse[i][j] = min(sparse[i][j], sparse[p][j-1]);
}
}
}
int query(int l, int r)
{
int x = __lg(r-l+1);
return min(sparse[l][x], sparse[r-(1<<x)+1][x]);
}
};
vector<int> t, h;
SparseTable st;
SparseTableMin stm;
void initialize(vector<int> T, vector<int> H) {
t = T; h = H;
st.init(h); stm.init(h);
}
bool can_reach(int L, int R, int S, int D) {
//Subtask 3
if(S > D) swap(S, D);
int m = h.size();
int l = 0, r = S, p = 0;
while(l <= r){
int mid = (l+r)/2;
if(st.query(mid, S) >= t[0]) l = mid+1;
else{p = mid; r = mid-1;}
}
int l1 = p;
l = S, r = m-1, p = 0;
while(l <= r){
int mid = (l+r)/2;
if(st.query(S, mid) >= t[0]) r = mid-1;
else{p = mid; l = mid+1;}
}
int r1 = p;
l = 0, r = D, p = 0;
while(l <= r){
int mid = (l+r)/2;
if(st.query(mid, D) >= t[0]) l = mid+1;
else{p = mid; r = mid-1;}
}
int l2 = p;
l = D, r = m-1, p = 0;
while(l <= r){
int mid = (l+r)/2;
if(st.query(D, mid) >= t[0]) r = mid-1;
else{p = mid; l = mid+1;}
}
int r2 = p;
/**/
if(r1 >= l2) return 1;
if(stm.query(l1, r1) > 0 || stm.query(l2, r2) > 0) return 0;
if(st.query(S, D) < 3) return 1;
else return 0;
}
