#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
const int INF = 1e9;
struct node {
int left = -1;
int right = -1;
};
vector<node> nodes;
vector<int> height_to_index(262144 + 10);
vector< vector<int> > binary_lifting(262144 + 10, vector<int>(30, -1)); // It tells you the height of the 2^jth ancestor of i.
void init(int N, vector<int> H) {
n = N;
h = H;
nodes = vector<node>(n); // It's a graph, has the index to the children.
for (int i = 1; i < n; i++) {
int target = i - 1;
while (H[target] <= H[i]) {
if (target == -1) {
break;
}
target = nodes[target].left;
}
nodes[i].left = target;
}
for (int i = n - 2; i >= 0; i--) {
int target = i + 1;
while (H[target] <= H[i]) {
if (target == -1) {
break;
}
target = nodes[target].right;
}
nodes[i].right = target;
}
// Create the binary_lift
// Create the base ancestors;
for (int i = 0; i < n; i++) {
binary_lifting[i][0] = max(nodes[i].left, nodes[i].right);
}
for (int i = 1; i < 30; i++) {
for (int j = 0; j < n; j++) {
if (binary_lifting[j][i - 1] == -1) {
binary_lifting[j][i] = -1;
}
else {
binary_lifting[j][i] = binary_lifting[binary_lifting[j][i - 1]][i - 1];
}
}
}
for (int i = 0; i < n; i++) {
height_to_index[h[i]]= i;
}
// cout << "Ancestor: " << binary_lifting[1][1] << '\n';
return;
}
// Return the index of the closest approximate of how many to jump.
int final_index;
int closest(int source, int height) {
int high = 29;
int low = 0;
int ans = -1;
// Find the greatest ancestor that doesn't exceed or equal the height
// In theory, if the source is too large, then it should just return 0.
while (low <= high) {
int mid = (low + high) / 2;
if (binary_lifting[source][mid] != -1 && binary_lifting[source][mid] < height) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
cout << "ANS: " << ans << '\n';
if (ans == -1) {
// My parent is already optimal.
return -1;
}
int child_ans = closest(binary_lifting[source][ans], height - (1<<ans));
if (child_ans == -1) {
// My children thinks I am the optimal one.
final_index = height_to_index[binary_lifting[source][ans]];
return 1<<ans; // The amount I jumped.
}
else {
return (1<<ans) + child_ans;
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (A != B || C != D) {
return -1;
}
// Find the greatest height only using the greater neighbour that does not exceed C.
int closest_amount = closest(A, h[C]);
cout << final_index << '\n';
if ((nodes[final_index].left + closest_amount + h[A]) == h[C] || (nodes[final_index].right + closest_amount + h[A]) == h[C]) {
return closest_amount + 1;
}
else {
return -1;
}
}
