#pragma GCC optimize("Ofast")
#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cout if(0) cout
struct SegTree {
v<int> tree;
v<int> mx;
SegTree() {}
SegTree(int n) {
tree.assign(4*n, 1e9);
mx.assign(4*n, 0);
}
void build(int p, int l, int r, int i, int x) {
if (l > i || r < i) return;
if (l == r && r == i) {
tree[p] = x;
mx[p] = x;
}
else {
build(2*p, l, (l+r)/2, i, x);
build(2*p+1, (l+r)/2+1, r, i, x);
tree[p] = min(tree[2*p], tree[2*p+1]);
mx[p] = max(mx[2*p], mx[2*p+1]);
}
}
int query(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 1e9;
if (i <= l && r <= j) return tree[p];
else {
int i1 = query(2*p, l, (l+r)/2, i, j);
int i2 = query(2*p+1, (l+r)/2+1, r, i, j);
return min(i1, i2);
}
}
int maxx(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (i <= l && r <= j) return mx[p];
else {
int i1 = maxx(2*p, l, (l+r)/2, i, j);
int i2 = maxx(2*p+1, (l+r)/2+1, r, i, j);
return max(i1, i2);
}
}
};
int N, M;
SegTree stT, stH;
v<int> t, h;
v<int> sig;
v<v<int>> liftleft;
v<v<int>> liftright;
void initialize(std::vector<int> T, std::vector<int> H) {
t = T;
h = H;
N = T.size();
M = H.size();
//rep(i, 0, N) {rep(j, 0, M) {if (T[i] > H[j]) cout << 1 << " ";else cout << 0 << " ";}cout << endl;}
stT = SegTree(N);
stH = SegTree(M);
rep(i, 0, N) {
stT.build(1, 0, N-1, i, T[i]);
}
rep(i, 0, M) {
stH.build(1, 0, M-1, i, H[i]);
}
liftleft.assign(M, v<int>(20, 1e9));
liftright.assign(M, v<int>(20, 1e9));
rep(i, 0, M) {
if (i > 0) liftleft[i][0] = H[i-1];
if (i < M-1) liftright[i][0] = H[i+1];
}
rep(j, 1, 20) {
rep(i, 0, M) {
if (i - (1 << (j-1)) > 0) liftleft[i][j] = max(liftleft[i - (1 << (j-1))][j-1], liftleft[i][j-1]);
if (i + (1 << (j-1)) < M) {
if (j == 2 && i == 1) {
cout << liftright[i+(1<<(j-1))][j-1] << " " << liftright[i][j-1] << endl;
}
liftright[i][j] = max(liftright[i + (1 << (j-1))][j-1], liftright[i][j-1]);
}
}
}
stack<int> s;
stack<int> idx;
sig.assign(N, -1);
rep(i, 0, N) {
while (s.size() && T[i] > s.top()) {
sig[idx.top()] = i;
idx.pop();
s.pop();
}
s.push(T[i]);
idx.push(i);
}
return;
}
bool salto_valido(int row1, int row2, int l, int r) {
int mnH = stH.query(1, 0, M-1, l, r);
int mnT = stT.query(1, 0, N-1, row1, row2);
if (mnT > mnH) return true;
else return false;
}
pair<int, int> find_range(int S) {
int row = 0;
int l, r;
l = r = S;
for (int i = 19; i >= 0; i--) {
if (liftleft[l][i] < t[row]) {
l -= (1 << i);
}
}
for (int i = 19; i >= 0; i--) {
if (liftright[r][i] < t[row]) {
r += (1 << i);
}
}
while (sig[row] != -1 && salto_valido(row, sig[row], l, r)) {
row = sig[row];
cout << l << " "<< r << endl;
for (int i = 19; i >= 0; i--) {
if (liftleft[l][i] < t[row]) {
l -= (1 << i);
}
}
for (int i = 19; i >= 0; i--) {
cout << r << " " << i << " " << liftright[r][i] << endl;
if (liftright[r][i] < t[row]) {
r += (1 << i);
cout << i << endl;
}
}
}
return {l, r};
}
bool can_reach(int L, int R, int S, int D) {
int l1, r1;
auto aux = find_range(S);
l1 = aux.first, r1 = aux.second;
int l2, r2;
aux = find_range(D);
l2 = aux.first, r2 = aux.second;
//cout << l1 << " "<< r1 << " " << l2 << " "<< r2 << endl;
if (l1 == l2 && r1 == r2) return true;
else return false;
}
