#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]);
}
vector<pair<int, int>> normalized(vector<pair<int, int>> a) {
if (a.empty())
return {};
vector<pair<int, int>> ans;
ans.push_back(a[0]);
pair<int, int> p;
for (int i = 1; i < a.size(); i++)
if (ans[ans.size()-1].second == a[i].first-1) {
p.first = ans.back().first;
p.second = a[i].second;
ans.pop_back();
ans.push_back(p);
} else
ans.push_back(a[i]);
return ans;
}
vector<pair<int, int>> query(int u, int l, int r, int val) {
//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";
return {make_pair(l, r)};
}
if (l == r)
return {};
int mid = (l+r)/2;
vector<pair<int, int>> a = query(2*u, l, mid, val);
vector<pair<int, int>> b = query(2*u + 1, mid+1, r, val);
a.insert(a.end(), b.begin(), b.end());
return a;
}
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]);
//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]);
}
