#include <bits/stdc++.h> using namespace std; const int LOG = 20; int N, M; vector<int> T, H, pref; vector<vector<int>> mx, mn, mxT; void initialize(vector<int> T, vector<int> H) { N = (int)T.size(), M = (int)H.size(); ::T.resize(N); ::H.resize(M); pref.resize(N); mx.resize(LOG, vector<int> (M)); mn.resize(LOG, vector<int> (M)); mxT.resize(LOG, vector<int> (N)); for(int i = 0; i < N; i++){ ::T[i] = T[i]; mxT[0][i] = T[i]; if(!i) pref[i] = T[i]; else pref[i] = min(pref[i - 1], T[i]); } for(int i = 0; i < M; i++){ ::H[i] = H[i]; mx[0][i] = H[i]; mn[0][i] = H[i]; } for(int i = 1; i < LOG; i++){ for(int j = 0; j + (1 << i) <= M; j++){ mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]); mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]); } for(int j = 0; j + (1 << i) <= N; j++){ mxT[i][j] = max(mxT[i - 1][j], mxT[i - 1][j + (1 << (i - 1))]); } } } bool check(int &temp, int &start, int &end){ int k = 31 - __builtin_clz(end - start + 1); return temp > max(mx[k][start], mx[k][end - (1 << k) + 1]); } bool can_reach(int LL, int RR, int S, int D) { if(S > D) swap(S, D); int i = 0, j = S; while(1){ int L = i, R = N - 1, res; while(L <= R){ int mid = L + (R - L) / 2; if(pref[mid] > H[j]){ res = mid; L = mid + 1; } else{ R = mid - 1; } } int d = 31 - __builtin_clz(res - i + 1); int maxT = max(mxT[d][i], mxT[d][res - (1 << d) + 1]); while(T[i] != maxT) i++; L = j, R = D, res; while(L <= R){ int mid = L + (R - L) / 2; if(check(T[i], j, mid)){ res = mid; L = mid + 1; } else{ R = mid - 1; } } if(res == j) return 0; if(res >= D) return 1; int k = 31 - __builtin_clz(res - j + 1); int minH = min(mn[k][j], mn[k][res - (1 << k) + 1]); if(H[j] == minH) return 0; while(H[j] != minH) j++; } }