#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
vector<int>t, h;
int n, m, l, r, s, d;
bool is_sub12 = false;
namespace sub12{
bool check_subtask(){
for(int i = 1; i < n; i++){
if(t[i - 1] > t[i]){
return false;
}
}
return true;
}
vector<int>lab;
int find_set(int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
}
void init(){
lab.resize(m);
iota(lab.begin(), lab.end(), 0);
for(int i = 1; i < m; i++){
if(t[n - 1] > max(h[i], h[i - 1])){
lab[i] = find_set(i - 1);
}
}
}
bool solve(){
return find_set(s) == find_set(d);
}
}
namespace sub3{
vector<int>color[3];
void dfs(int x, int y, const int c){
if(x < 0 || x >= n || y < 0 || y >= m || color[x][y] != -1 || t[x] <= h[y]){
return;
}
dfs(x - 1, y, color[x][y] = c);
dfs(x + 1, y, c);
dfs(x, y - 1, c);
dfs(x, y + 1, c);
}
void init(){
for(int i = 0; i < 3; i++){
color[i].assign(m, -1);
}
for(int i = 0, cnt = 0; i < 3; i++){
for(int j = 0; j < m; j++){
if(color[i][j] == -1 && t[i] > h[j]){
dfs(i, j, cnt++);
}
}
}
}
bool solve(){
return color[0][s] == color[0][d];
}
}
struct SparseTable{
vector<int>lgv, spt[18];
void build(const vector<int>& a){
int n = a.size();
lgv.resize(n + 1);
lgv[0] = -1;
for(int i = 1; i <= n; i++){
lgv[i] = lgv[i >> 1] + 1;
}
spt[0] = a;
for(int i = 1; i < 18; i++){
for(int j = 0; j + (1 << i) - 1 < n; j++){
spt[i].push_back(max(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]));
}
}
}
int get(int l, int r){
int k = lgv[r - l + 1];
return max(spt[k][l], spt[k][r - (1 << k) + 1]);
}
};
SparseTable hmax;
namespace sub45{
struct Data{
int l, r, vmin;
Data(){}
Data(int _l, int _r, int _vmin) : l(_l), r(_r), vmin(_vmin) {}
friend bool operator <(Data a, Data b){
return a.vmin > b.vmin || (a.vmin == b.vmin && a.l > b.l);
}
};
vector<int>ptmax, best_t;
void init(){
hmax.build(h);
ptmax = t;
for(int i = 1; i < n; i++){
maximize(ptmax[i], ptmax[i - 1]);
}
set<Data>s;
vector<int>L(m), R(m), V(m), pm(m);
for(int i = 0; i < m; i++){
s.insert(Data(i, i, V[L[i] = R[i] = pm[i] = i] = h[i]));
}
auto find_set = [&] (int i){
while(i != L[i]){
i = L[i] = L[L[i]];
}
return i;
};
auto erase_set = [&] (int l, int r, int v){
auto it = s.find(Data(l, r, v));
if(it != s.end()){
s.erase(it);
}
};
auto merge = [&] (int i, int j){
if((i = find_set(i)) != (j = find_set(j))){
if(i > j){
swap(i, j);
}
erase_set(L[i], R[i], V[i]);
erase_set(L[j], R[j], V[j]);
maximize(R[L[j] = i], R[j]);
minimize(V[i], V[j]);
s.insert(Data(L[i], R[i], V[i]));
}
};
set<int>consider;
for(int i = 0; i < m; i++){
if(t[0] > h[i]){
consider.insert(i);
}
}
sort(pm.begin(), pm.end(), [&] (int i, int j){
return h[i] < h[j];
});
best_t.assign(m, n - 1);
for(int i = 1, p = 0; i < n; i++){
while(p < m && h[pm[p]] < t[i]){
int j = pm[p++];
if(j > 0 && h[j - 1] < t[i]){
merge(j - 1, j);
}
if(j + 1 < m && h[j + 1] < t[i]){
merge(j, j + 1);
}
}
vector<Data>trash;
for(const Data& it : s){
if(it.vmin < t[i]){
break;
}
for(auto itc = consider.lower_bound(it.l); itc != consider.end() && *itc <= it.r; itc++){
best_t[*itc] = i - 1;
}
consider.erase(consider.lower_bound(it.l), consider.upper_bound(it.r));
trash.push_back(it);
}
for(Data& it : trash){
s.erase(it);
}
}
}
bool solve(){
return ptmax[min(best_t[s], best_t[d])] > hmax.get(s, d);
}
}
namespace sub6{
const int lim = 2e5 + 5;
vector<int>ptmin, ptmax;
int best_t[lim], gol[18][lim], gor[18][lim], best_l[18][lim], best_r[18][lim];
void init(){
hmax.build(h);
ptmin = ptmax = t;
for(int i = 1; i < n; i++){
minimize(ptmin[i], ptmin[i - 1]);
maximize(ptmax[i], ptmax[i - 1]);
}
for(int i = 0; i < m; i++){
int low = 0, high = n - 1, pos = -1;
while(low <= high){
int mid = (low + high) >> 1;
if(ptmin[mid] <= h[i]){
high = mid - 1;
}
else{
low = (pos = mid) + 1;
}
}
best_t[i] = pos == -1 ? 0 : ptmax[pos];
}
vector<int>stk, L(m), R(m);
for(int i = 0; i < m; stk.push_back(i++)){
while(!stk.empty() && h[stk.back()] >= h[i]){
stk.pop_back();
}
L[i] = stk.empty() ? -1 : stk.back();
}
stk.clear();
for(int i = m - 1; i > -1; stk.push_back(i--)){
while(!stk.empty() && h[stk.back()] >= h[i]){
stk.pop_back();
}
R[i] = stk.empty() ? -1 : stk.back();
}
for(int i = 0; i < m; i++){
bool can_l = L[gol[0][i] = gor[0][i] = i] != -1 && hmax.get(L[i], i) < best_t[i], can_r = R[i] != -1 && hmax.get(i, R[i]) < best_t[i];
if(can_l){
gol[0][i] = L[i];
}
else if(can_r){
gol[0][i] = R[i];
}
if(can_r){
gor[0][i] = R[i];
}
else if(can_l){
gor[0][i] = L[i];
}
best_l[0][i] = min(i, gor[0][i]);
best_r[0][i] = max(i, gol[0][i]);
}
for(int i = 1; i < 18; i++){
for(int j = 0; j < m; j++){
gol[i][j] = gol[i - 1][gol[i - 1][j]];
gor[i][j] = gor[i - 1][gor[i - 1][j]];
best_l[i][j] = min(best_l[i - 1][j], best_l[i - 1][gor[i - 1][j]]);
best_r[i][j] = max(best_r[i - 1][j], best_r[i - 1][gol[i - 1][j]]);
}
}
}
bool solve(){
int init_s = s, init_d = d;
for(int i = 17; i > -1; i--){
if(best_l[i][s] >= l){
s = gor[i][s];
}
}
for(int i = 17; i > -1; i--){
if(best_r[i][d] <= r){
d = gol[i][d];
}
}
return hmax.get(min(s, init_d), max(s, init_d)) < best_t[s] && hmax.get(min(init_s, d), max(init_s, d)) < best_t[d];
}
}
void initialize(vector<int>_t, vector<int>_h){
swap(t, _t);
swap(h, _h);
n = t.size();
m = h.size();
if(is_sub12 = sub12::check_subtask()){
sub12::init();
}
else if(n == 3){
sub3::init();
}
else{
sub45::init();
sub6::init();
}
}
bool can_reach(int _l, int _r, int _s, int _d){
l = _l;
r = _r;
if((s = _s) > (d = _d)){
swap(s, d);
}
if(l == 0 && r == m - 1){
if(is_sub12){
return sub12::solve();
}
if(n == 3){
return sub3::solve();
}
return sub45::solve();
}
return sub6::solve();
}
