#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
void file() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
#define all(v) v.begin(),v.end()
#define pb push_back
#define V vector
#define P pair
#define F first
typedef long long ll;
int mx[(int)2e5+1][20];
int imx[(int)2e5+1][20];
int imn[(int)2e5+1][20];
int mn[(int)2e5+1][20];
int lg[(int)2e5+1];
int mn1[(int)2e5+1][20];
int imx1[(int)2e5+1][20];
int mx1[(int)2e5+1][20];
int t[(int)2e5+1];
int h[(int)2e5+1];
int n,m;
int dp[(int)2e5+1];
void init(int s) {
for (int i=0;i<s;i++) {
mx[i][0]=h[i];
imx[i][0]=i;
imn[i][0]=i;
mn[i][0]=h[i];
}
for (int k=1;k<20;k++) {
for (int i=0;i<s;i++) {
if (i+(1<<k)-1<s) {
mx[i][k]=max(mx[i][k-1],mx[i+(1<<(k-1))][k-1]);
if (mx[i][k-1]>=mx[i+(1<<(k-1))][k-1]) {
imx[i][k]=imx[i][k-1];
}
else {
imx[i][k]=imx[i+(1<<(k-1))][k-1];
}
mn[i][k]=min(mn[i][k-1],mn[i+(1<<(k-1))][k-1]);
if (mn[i][k-1]<=mn[i+(1<<(k-1))][k-1]) {
imn[i][k]=imn[i][k-1];
}
else {
imn[i][k]=imn[i+(1<<(k-1))][k-1];
}
}
}
}
}
void init1(int s) {
for (int i=0;i<s;i++) {
imx1[i][0]=i;
mx1[i][0]=t[i];
mn1[i][0]=t[i];
}
for (int k=1;k<20;k++) {
for (int i=0;i<s;i++) {
if (i+(1<<k)-1<s) {
mx1[i][k]=max(mx1[i][k-1],mx1[i+(1<<(k-1))][k-1]);
if (mx1[i][k-1]>=mx1[i+(1<<(k-1))][k-1]) {
imx1[i][k]=imx1[i][k-1];
}
else {
imx1[i][k]=imx1[i+(1<<(k-1))][k-1];
}
mn1[i][k]=min(mn1[i][k-1],mn1[i+(1<<(k-1))][k-1]);
}
}
}
}
int qmn1(int l,int r) {
int x=lg[r-l+1];
return min(mn1[l][x],mn1[r-(1<<x)+1][x]);
}
int qmx1(int l,int r) {
int x=lg[r-l+1];
if (mx1[l][x]>=mx1[r-(1<<x)+1][x]) {
return imx1[l][x];
}
return imx1[r-(1<<x)+1][x];
}
int qmx(int l,int r) {
int x=lg[r-l+1];
return max(mx[l][x],mx[r-(1<<x)+1][x]) ;
}
int qmn(int l,int r) {
int x=lg[r-l+1];
if (mn[l][x]<=mn[r-(1<<x)+1][x]) {
return imn[l][x];
}
return imn[r-(1<<x)+1][x];
}
bool check(int i,int l,int r) {
if (l>=r) {
swap(l,r);
}
int x=qmx(l,r);
if (x<t[i])return true;
return false;
}
void initialize(std::vector<int> T, std::vector<int> H) {
lg[1]=0;
for (int i=2;i<=(int)2e5;i++) {
lg[i]=lg[i/2]+1;
}
n=(int)T.size();
m=(int)H.size();
V<P<int,int>>a(m);
for (int i=0;i<n;i++) {
t[i]=T[i];
}
for (int i=0;i<m;i++) {
h[i]=H[i];
a[i].second=i;
a[i].first=h[i];
}
init(m);
init1(n);
sort(all(a));
for (auto u:a) {
int id=u.second;
if (h[id]>=t[0])continue;
int l=0,r=n-1;
int ans=-1;
while (l<=r) {
int mid=l+(r-l)/2;
if (qmn1(0,mid)>h[id]) {
ans=mid;
l=mid+1;
}
else {
r=mid-1;
}
}
int id1=qmx1(0,ans);
l=id,r=m-1;
int ans1=-1;
while (l<=r) {
int mid=l+(r-l)/2;
if (qmx(id,mid)<t[id1]) {
ans1=mid;
l=mid+1;
}
else
r=mid-1;
}
l=0,r=id;
int ans2=-1;
while (l<=r) {
int mid=l+(r-l)/2;
if (qmx(mid,id)<t[id1]) {
ans2=mid;
r=mid-1;
}
else {
l=mid+1;
}
}
int id2=qmn(ans2,ans1);
if (h[id2]<h[id]) {
dp[id]=dp[id2];
}
else {
dp[id]=id1;
}
}
}
bool can_reach(int L, int R, int S, int D) {
if (S>D) {
swap(S,D);
}
int x=min(t[dp[S]],t[dp[D]]);
if (qmx(S,D)<x) {
return true;
}
return false;
}
