#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> next_greater(const vector<int> &v) {
int n = v.size();
vector<int> ans(n, -1);
vector<int> possible_next{n-1};
for (int i = n-2; i >= 0; --i) {
while (!possible_next.empty() && v[i] >= v[possible_next.back()]) possible_next.pop_back();
if (!possible_next.empty()) ans[i] = possible_next.back();
possible_next.push_back(i);
}
return ans;
}
using interval = pair<int, int>;
interval onion(interval a, interval b) {
return {min(a.first, b.first), max(a.second, b.second)};
}
bool has_overlap(interval a, interval b) {
return !(a.second < b.first || b.second < a.first);
}
// fn ((a, b), (a, b)) { (a, b) }
// let onion((x, y), (z, w)) = (min(x, z), max(y, w))
struct Jumper {
vector<vector<int>> tree_ch;
vector<vector<int>> locations;
vector<vector<pair<int, int>>> ranges_crossed;
void find_ranges(int v) {
auto &reachable_ranges = ranges_crossed[0];
reachable_ranges[v] = {v, v};
for (int ch : tree_ch[v]) {
find_ranges(ch);
reachable_ranges[v] = onion(reachable_ranges[v], reachable_ranges[ch]);
}
for (int ch : tree_ch[v]) {
reachable_ranges[ch] = onion(reachable_ranges[ch], pair{min(ch, v), max(ch, v)});
}
}
Jumper() {}
Jumper(int root, const vector<int> &tree) : tree_ch(tree.size()), locations(20, vector(tree.size(), -1)),
ranges_crossed(20, vector(tree.size(), pair<int, int>{tree.size() + 100, -1})) {
for (int i = 0; i < tree.size(); ++i) if (tree[i] != -1) {
tree_ch[tree[i]].push_back(i);
locations[0][i] = tree[i];
}
find_ranges(root);
for (int i = 0; i < tree.size(); ++i) {
int layer = 0;
// cerr << "layer " << layer << " " << i << " -> " << locations[layer][i] << " (" << ranges_crossed[layer][i].first << ", " << ranges_crossed[layer][i].second << ")" << endl;
}
for (int layer = 1; layer < locations.size(); ++layer) {
for (int i = 0; i < tree.size(); ++i) if (locations[layer-1][i] != -1) {
locations[layer][i] = locations[layer-1][locations[layer-1][i]];
ranges_crossed[layer][i] = onion(ranges_crossed[layer-1][i], ranges_crossed[layer-1][locations[layer-1][i]]);
// cerr << "layer " << layer << " " << i << " -> " << locations[layer][i] << " (" << ranges_crossed[layer][i].first << ", " << ranges_crossed[layer][i].second << ")" << endl;
}
}
}
int last_inside(int v, interval i) {
int cv = v;
for (int layer = locations.size() - 1; layer >= 0; --layer) {
if (locations[layer][cv] != -1 && i.first <= locations[layer][cv] && locations[layer][cv] <= i.second) cv = locations[layer][cv];
}
return cv;
}
// {vertex, # of steps taken}
pair<int, int> last_before_overlapping(int v, interval i) {
int cv = v;
auto crange = ranges_crossed[0][v];
int dist = 0;
for (int layer = locations.size() - 1; layer >= 0; --layer) {
if (locations[layer][cv] != -1 && !has_overlap(onion(crange, ranges_crossed[layer][cv]), i)) {
crange = onion(crange, ranges_crossed[layer][cv]);
cv = locations[layer][cv];
dist += (1 << layer);
}
}
return {cv, dist};
}
int parent(int v) {
return locations[0][v];
}
};
Jumper fast, slow;
void init(int N, std::vector<int> H) {
// impl detail so ng and pg are always defined on nodes that matter
vector<int> ng = next_greater(H);
reverse(H.begin(), H.end());
vector<int> pg = next_greater(H); reverse(H.begin(), H.end());
reverse(pg.begin(), pg.end());
for (int &v : pg) v = (v == -1 ? -1 : N - 1 - v);
vector<int> fast_tree(N, -1), slow_tree(N, -1);
for (int i = 0; i < N; ++i) {
if (ng[i] == -1 && pg[i] == -1) continue;
else if (ng[i] == -1 || pg[i] == -1) {
int par = max(ng[i], pg[i]);
fast_tree[i] = slow_tree[i] = par;
} else {
pair<int, int> target1 = {H[ng[i]], ng[i]}, target2 = {H[pg[i]], pg[i]};
if (target1 > target2) swap(target1, target2);
fast_tree[i] = target2.second;
slow_tree[i] = target1.second;
}
// cerr << "jump targets: " << fast_tree[i] << " " << slow_tree[i] << endl;
}
int max_idx = distance(begin(H), max_element(begin(H), end(H)));
// cerr << " == processing fast tree " << endl;
fast = Jumper(max_idx, fast_tree);
// cerr << " == processing slow tree " << endl;
slow = Jumper(max_idx, slow_tree);
}
int minimum_jumps(int A, int B, int C, int D) {
int src = slow.last_inside(A, {A, B});
// cerr << " starting from " << src << endl;
auto [v1, dist1] = fast.last_before_overlapping(src, {C, D});
// cerr << " phase 1: " << v1 << endl;
auto [v2, dist2] = slow.last_before_overlapping(v1, {C, D});
// cerr << " phase 2: " << v2 << endl;
int pot_dst = slow.parent(v2);
if (C <= pot_dst && pot_dst <= D) return dist1 + dist2 + 1;
else return -1;
}
// 3 2 1 6 4 5 7
