#include "obstacles.h"
#include <bits/stdc++.h>
//#include <cassert>
//#include <cstdio>
using namespace std;
int n, m;
vector <int> t, h;
bool group1b = false;
vector <int> group1;
bool group2b = false;
vector <int> group2;
bool group3b = false;
vector <pair <int, int>> group30;
vector <int> group31, group32, group33;
void initialize ( vector <int> T, vector <int> H ) {
n = T.size(), m = H.size();
t = T, h = H;
if ( n == 1 ) {
group1b = true;
group1.resize( m );
for ( int i = 0; i < m; i++ ) {
group1[i] = -1;
if ( i != 0 ) {
group1[i] = group1[i - 1];
}
if ( t[0] <= h[i] ) {
group1[i] = i;
}
}
} else if ( n == 3 and t[0] == 2 and t[1] == 1 and t[2] == 3 ) {
group30.resize( m ), group31.resize( m ), group32.resize( m ), group33.resize( m );
for ( int i = 0; i < m; i++ ) {
group30[i].first = -1;
if ( i != 0 ) {
group30[i].first = group30[i - 1].first;
group31[i] = group31[i - 1];
group32[i] = group32[i - 1];
group33[i] = group33[i - 1];
}
if ( h[i] == 0 ) {
group30[i].first = i;
} else if ( h[i] == 1 ) {
group31[i]++;
} else if ( h[i] == 2 ) {
group32[i]++;
} else {
group33[i]++;
}
}
for ( int i = m - 1; i >= 0; i-- ) {
group30[i].second = -1;
if ( i != m - 1 ) {
group30[i].second = group30[i + 1].second;
}
if ( h[i] == 0 ) {
group30[i].second = i;
}
}
group3b = true;
} else {
group2b = true;
group2.resize( m );
for ( int i = 0; i < m; i++ ) {
group2[i] = -1;
if ( i != 0 ) {
group2[i] = group2[i - 1];
}
if ( t[n - 1] <= h[i] ) {
group2[i] = i;
}
}
}
return;
}
bool can_reach ( int l, int r, int s, int d ) {
if ( s > d ) {
swap ( s, d );
}
if ( group1b == true ) {
if ( group1[d] >= s ) {
return false;
} else {
return true;
}
} else if ( group2b == true ) {
if ( group2[d] >= s ) {
return false;
} else {
return true;
}
} else {
int k1 = group32[d] - group32[s] + group33[d] - group33[s];
if ( k1 == 0 ) {
return true;
}
if ( group30[s].first != -1 and group30[d].first != -1 ) {
int l = group30[s].first, r = group30[d].first;
if ( l > r ) {
swap ( l, r );
}
int k = group32[s] - group32[l] + group32[d] - group32[r];
k += group33[s] - group33[l] + group33[d] - group33[r];
if ( k <= 0 and l != r ) {
k = group33[r] - group33[l];
if ( k <= 0 ) {
return true;
}
}
}
if ( group30[s].first != -1 and group30[d].second != -1 ) {
int l = group30[s].first, r = group30[d].second;
if ( l > r ) {
swap ( l, r );
}
int k = group32[s] - group32[l] + group32[r] - group32[d];
k += group33[s] - group33[l] + group33[r] - group33[d];
if ( k <= 0 and l != r ) {
k = group33[r] - group33[l];
if ( k <= 0 ) {
return true;
}
}
}
if ( group30[s].second != -1 and group30[d].second != -1 ) {
int l = group30[s].second, r = group30[d].second;
if ( l > r ) {
swap ( l, r );
}
int k = group32[l] - group32[s] + group32[r] - group32[d];
k += group33[l] - group33[s] + group33[r] - group33[d];
if ( k <= 0 and l != r ) {
k = group33[r] - group33[l];
if ( k <= 0 ) {
return true;
}
}
}
if ( group30[s].second != -1 and group30[d].first != -1 ) {
int l = group30[s].second, r = group30[d].first;
if ( l > r ) {
swap ( l, r );
}
int k = group32[l] - group32[s] + group32[d] - group32[r];
k += group33[l] - group33[s] + group33[d] - group33[r];
if ( k <= 0 and l != r ) {
k = group33[r] - group33[l];
if ( k <= 0 ) {
return true;
}
}
}
return false;
}
return true;
}
/*int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> T(N), H(M);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &T[i]));
for (int i = 0; i < M; i++)
assert(1 == scanf("%d", &H[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> L(Q), R(Q), S(Q), D(Q);
for (int i = 0; i < Q; i++)
assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i]));
fclose(stdin);
std::vector<bool> A(Q);
initialize(T, H);
for (int i = 0; i < Q; i++)
A[i] = can_reach(L[i], R[i], S[i], D[i]);
for (int i = 0; i < Q; i++)
if (A[i])
printf("1\n");
else
printf("0\n");
fclose(stdout);
return 0;
}*/
