#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <iomanip>
#include <queue>
#include <stack>
#include <numeric>
#include <cassert>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
// #define sz(x) ((int)x.size())
#define rep(i, a, b) for(int i = a; i < b; ++i)
template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif
template <typename T>
void remove_duplicates(vector<T> &v){
sort(all(v));
v.resize(unique(all(v)) - v.begin());
}
template <typename T> void chmin(T &a, T b){ a = (b < a) ? b : a; }
template <typename T> void chmax(T &a, T b){ a = (b > a) ? b : a; }
int n, m;
vi t, h;
const int N = 2e5 + 3;
const int INF = 1e9;
struct SegmentTree {
vector<int> mn;
int sz;
SegmentTree(int sz): sz(sz) {
mn.resize(sz);
}
void update(int idx, int val, int i, int l, int r) {
if (r < idx || idx < l) {
return;
}
if (l == r) {
mn[i] = val;
return;
}
int mid = (l + r) >> 1;
update(idx, val, 2 * i + 1, l, mid);
update(idx, val, 2 * i + 2, mid + 1, r);
mn[i] = min(mn[2 * i + 1], mn[2 * i + 2]);
}
int query(int sl, int sr, int i, int l, int r) {
if (r < sl || sr < l) {
return INF;
}
if (sl <= l && r <= sr) {
return mn[i];
}
int mid = (l + r) >> 1;
return min(query(sl, sr, 2 * i + 1, l, mid), query(sl, sr, 2 * i + 2, mid + 1, r));
}
int query(int sl, int sr) {
return query(sl, sr, 0, 0, sz - 1);
}
void update(int idx, int val) {
return update(idx, val, 0, 0, sz - 1);
}
} min_st_h(0);
int min_in_range(int l, int r) {
return min_st_h.query(l, r);
}
int expand_right(int r, int t_val) {
while (r < m - 1 && h[r + 1] < t_val) {
++r;
}
return r;
}
int expand_left(int l, int t_val) {
while (l > 0 && h[l - 1] < t_val) {
--l;
}
return l;
}
bool can_reach(int l, int r, int s, int d) {
if (s > d) {
swap(s, d);
}
// t[i] > s[j] -> free => t[i] - s[j] > 0
// 1. Find first biggest on the row in order to form the starting range
// 2. For each new row, either check if the min of the range is OK or check if you can expand the range
// 3. How to expand the range? check for larger numbers than t and expand to there.
// => Need first bigger than query
pair<int, int> range{s, s};
for (int i = 0; i < n; ++i) {
if (min_in_range(range.first, range.second) >= t[i]) {
return false;
}
range.first = expand_left(range.first, t[i]);
range.second = expand_right(range.second, t[i]);
debug(i, range);
if (range.first <= d && d <= range.second) {
return true;
}
}
return range.first <= d && d <= range.second;
}
void initialize(std::vector<int> T, std::vector<int> H) {
swap(t, T);
swap(h, H);
n = t.size();
m = h.size();
min_st_h = SegmentTree(m);
for (int i = 0; i < m; ++i) {
min_st_h.update(i, h[i]);
}
}
