#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int N, M;
vector<int> T(MAXN), H(MAXN), ST(4*MAXN);
int G[3][MAXN], id[3][MAXN];
int cnt = 0;
void dfs(int i, int j){
if(id[i][j] != -1) return;
id[i][j] = cnt;
if(i + 1 < 3 and G[i + 1][j] == 0){
dfs(i + 1, j);
}
if(i - 1 >= 0 and G[i - 1][j] == 0){
dfs(i - 1, j);
}
if(j + 1 < M and G[i][j + 1] == 0){
dfs(i, j + 1);
}
if(j - 1 >= 0 and G[i][j - 1] == 0){
dfs(i, j - 1);
}
}
void build(int v, int l, int r){
if(l == r){
ST[v] = H[l];
return;
}
int m = (l + r)/2;
build(2*v, l, m);
build(2*v + 1, m + 1, r);
ST[v] = max(ST[2*v], ST[2*v + 1]);
return;
}
int query(int v, int l, int r, int a, int b){
if(l > b or r < a) return 0;
if(l >= a and r <= b) return ST[v];
int m = (l + r)/2;
return max(query(2*v, l, m, a, b), query(2*v + 1, m + 1, r, a, b));
}
bool can_reach(int l, int r, int s, int d){
if(N == 3){
return id[0][s] == id[0][d];
}
if(d < s) swap(s, d);
if(query(1, 0, M - 1, s, d) >= T[N - 1]) return false;
else return true;
}
void initialize(vector<int> A, vector<int> B){
N = A.size(); M = B.size();
for(int i = 0; i < N; i++){
T[i] = A[i];
}
for(int i = 0; i < M; i++){
H[i] = B[i];
}
build(1, 0, M - 1);
if(N == 3){
memset(id, -1, sizeof(id));
for(int i = 0; i < M; i++){
if(H[i] >= 2){
G[0][i] = 1;
}
else G[0][i] = 0;
if(H[i] >= 1){
G[1][i] = 1;
}
else G[1][i] = 0;
if(H[i] >= 3){
G[2][i] = 1;
}
else G[2][i] = 0;
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < M; j++){
if(id[i][j] != -1) continue;
dfs(i, j);
cnt++;
}
}
}
}
