#include<bits/stdc++.h>
using namespace std;
const int mxN = 200000;
int seg_tree[4*mxN+1], n, color[mxN];
vector<pair<int, int>> empt[mxN];
void stree(int u, int l, int r, vector<int> &T) {
if (l >= n || r < 0 || l > r)
return;
if (l == r) {
seg_tree[u] = T[l];
return;
}
int mid = (l+r)/2;
stree(2*u, l, mid, T);
stree(2*u + 1, mid+1, r, T);
seg_tree[u] = min(seg_tree[2*u], seg_tree[2*u + 1]);
}
void query(int u, int l, int r, int val, vector<pair<int, int>> &ans) {
//cout<< '\n' << "QUERY. " << u << ' ' << l << ' ' << r << ' ' << val << ' ' << seg_tree[u] << '\n';
if (l >= n || r < 0 || l > r)
return;
if (seg_tree[u] > val) {
//cout<< "returned\n";
ans.push_back(make_pair(l, r));
return;
}
if (l == r)
return;
int mid = (l+r)/2;
query(2*u, l, mid, val, ans);
query(2*u + 1, mid+1, r, val, ans);
}
vector<pair<int, int>> transfer(vector<pair<int, int>> a, vector<pair<int, int>> b) {
vector<pair<int, int>> ans;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
// a -> b
while (!a.empty() && !b.empty()) {
pair<int, int> A = a.back();
pair<int, int> B = b.back();
if (A.first > B.second)
b.pop_back();
else if (B.first > A.second)
a.pop_back();
else {
ans.push_back(B);
b.pop_back();
}
}
return ans;
}
void initialize(vector<int> T, vector<int> H){
n = T.size();
memset(seg_tree, INT_MAX, sizeof seg_tree);
memset(color, -1, sizeof color);
stree(1, 0, n-1, T);
for (int i = 0; i < H.size(); i++) {
//cout<< i << " :\n";
//empt[i] = normalized(query(1, 0, n-1, H[i]));
//empt[i] = query(1, 0, n-1, H[i]);
query(1, 0, n-1, H[i], empt[i]);
sort(empt[i].begin(), empt[i].end());
//cout<< "\nempt\n";
//for (auto &[a, b] : empt[i]) {
// cout<< "\t(" << a << "; " << b << ")\n";
//}
}
map<int, int> to;
for (int i = 0; i < H.size(); i++)
to[i] = -1;
for (int i = 0; i < H.size(); i++) {
if (T[0] <= H[i])
continue;
if (color[i] == -1) {
color[i] = i;
vector<pair<int, int>> opn = empt[i];
for (int j = i+1; j < H.size(); j++) {
opn = transfer(opn, empt[j]);
if (opn.empty())
break;
if (opn[0].first == 0) {
if (color[j] != -1) {
to[i] = color[j];
break;
}
color[j] = i;
}
}
}
}
for (int i = 0; i < H.size(); i++)
if (color[i] != -1)
color[i] = max(color[i], to[color[i]]);
vector<int> bt(H.size(), 0);
/*
cout<< "COLOR :\n";
for (int i = 0; i < H.size(); i++)
cout<< color[i] << ' ';
cout<< '\n';
*/
}
bool can_reach(int L, int R, int S, int D){
return (color[S] == color[D]);
}
