#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin())
#define sort_uniq(x) sort(all(x)), uniq(x)
#define no_el(x, y) x.find(y) == x.end()
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define sz(x) int(x.size())
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)
#define ld long double
struct node{
int ind, l, r, t;
};
const int N = 2e5 + 5;
const int LG = 19;
int n, m;
V<int> t, h;
int stmn[N][LG], stmx[N][LG], tmn[N][LG], tmx[N][LG], lg2[N], nd[N];
V<node> v;
int p[N];
int sz[N];
bool vis[N * LG];
int timer = 1;
map<tuple<int, int, int>, int> mp;
void crt(int x) {
p[x] = x;
sz[x] = 1;
}
int find(int x) {
if (x == p[x]) return x;
return p[x] = x;
}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) {
return;
}
if (sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[b] = a;
}
int min_rng(int l, int r) {
int j = lg2[r - l + 1];
return min(stmn[l][j], stmn[r - (1 << j) + 1][j]);
}
int max_rng(int l, int r) {
int j = lg2[r - l + 1];
return max(stmx[l][j], stmx[r - (1 << j) + 1][j]);
}
int mnt_rng(int l, int r) {
int j = lg2[r - l + 1];
return min(tmn[l][j], tmn[r - (1 << j) + 1][j]);
}
int mxt_rng(int l, int r) {
int j = lg2[r - l + 1];
return max(tmx[l][j], tmx[r - (1 << j) + 1][j]);
}
void up(node x) {
vis[x.ind] = true;
if (x.l == 1 && x.r == m) return;
if (x.t == n) return;
int vl = min(h[x.l - 1], h[x.r - 1]);
if (mxt_rng(x.t + 1, n) <= vl) return;
int l = x.t + 1, r = n - 1, ans = n;
while (l <= r) {
int md = l + r >> 1;
if (mxt_rng(x.t + 1, md) <= vl) {
l = md + 1;
} else {
r = md - 1;
ans = md;
}
}
if (mnt_rng(x.t + 1, ans) <= min_rng(x.l, x.r))
return;
int nwt = ans;
l = 1, r = x.l - 1, ans = x.l;
while (l <= r) {
int md = l + r >> 1;
if (max_rng(md, x.l) < t[nwt]) {
r = md - 1;
ans = md;
} else {
l = md + 1;
}
}
int nwl = ans;
l = x.r + 1, r = m, ans = x.r;
while (l <= r) {
int md = l + r >> 1;
if (max_rng(x.r, md) < t[nwt]) {
l = md + 1;
ans = md;
} else {
r = md - 1;
}
}
int nwr = ans;
if (mp.find({nwt, nwl, nwr}) != mp.end()) {
merge(x.ind, mp[{nwt, nwl, nwr}]);
} else {
mp[{nwt, nwl, nwr}] = timer;
crt(timer);
++timer;
merge(x.ind, mp[{nwt, nwl, nwr}]);
up({timer - 1, nwl, nwr, nwt});
}
}
void initialize(std::vector<int> T, std::vector<int> H)
{
n = sz(T), m = sz(H);
t.resize(n + 1), h.resize(m + 1);
rep(i, 1, n, 1) t[i] = T[i - 1];
rep(i, 1, m, 1) h[i] = H[i - 1];
rep(i, 1, m, 1) {
stmn[i][0] = h[i];
stmx[i][0] = h[i];
}
rep(j, 1, LG - 1, 1) {
rep(i, 1, m, 1) {
int nx = i + (1 << (j - 1));
if (nx <= m) {
stmn[i][j] = min(stmn[i][j - 1], stmn[nx][j - 1]);
stmx[i][j] = max(stmx[i][j - 1], stmx[nx][j - 1]);
}
else {
stmn[i][j] = stmn[i][j - 1];
stmx[i][j] = stmx[i][j - 1];
}
}
}
rep(i, 1, m, 1) {
tmn[i][0] = t[i];
tmn[i][0] = t[i];
}
rep(j, 1, LG - 1, 1) {
rep(i, 1, m, 1) {
int nx = i + (1 << (j - 1));
if (nx <= m) {
tmn[i][j] = min(tmn[i][j - 1], tmn[nx][j - 1]);
tmn[i][j] = max(tmn[i][j - 1], tmn[nx][j - 1]);
}
else {
tmn[i][j] = tmn[i][j - 1];
tmn[i][j] = tmn[i][j - 1];
}
}
}
lg2[1] = 0;
rep(i, 2, N - 1, 1) {
lg2[i] = lg2[i >> 1] + 1;
}
int ls = 1;
bool las = false;
rep(i, 1, m, 1) {
if (t[1] > h[i]) {
nd[i] = timer;
las = true;
} else {
if (las) {
v.pb({timer, ls, i - 1, 1});
++timer;
}
ls = i + 1;
}
}
for (node x : v) {
crt(x.ind);
up(x);
}
}
bool can_reach(int l, int r, int s, int d) {
if (find(nd[s]) == find(nd[d])) return true;
else return false;
}
