#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< vector<int> > binary_lifting(262144 + 1, vector<int>(32, -1)); // It tells you the 2^j 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++) {
int greatest = -1;
int ancestor = -1;
if (nodes[i].left != -1 && greatest < H[nodes[i].left]) {
greatest = H[nodes[i].left];
ancestor = nodes[i].left;
}
if (nodes[i].right != -1 && greatest < H[nodes[i].right]) {
greatest = H[nodes[i].right];
ancestor = nodes[i].right;
}
binary_lifting[i][0] = ancestor;
}
for (int i = 1; i < 32; 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];
}
}
}
return;
}
int next_jump(int a, int c) {
if (a == -1) {
return -1;
}
int greatest = -1;
int ancestor = -1;
if (nodes[a].left != -1 && greatest < h[nodes[a].left] && h[nodes[a].left] <= h[c]) {
greatest = h[nodes[a].left];
ancestor = nodes[a].left;
}
if (nodes[a].right != -1 && greatest < h[nodes[a].right] && h[nodes[a].right] <= h[c]) {
greatest = h[nodes[a].right];
ancestor = nodes[a].right;
}
return ancestor;
}
// Gives the index to the jth ancestor
int find_ancestor(int source, int distance) {
int pos = source;
for (int i = 31; i >= 0; i--) {
if (distance & (1<<i)) {
pos = binary_lifting[pos][i];
if (pos == -1) {
return -1;
}
}
}
return pos;
}
int minimum_jumps(int A, int B, int C, int D) {
if (A != B || C != D) {
return -1;
}
int sum = 0;
bool found = false;
int X = A;
while (true) {
int high = 262144;
int low = 0;
int ans = -1;
while (low <= high) {
int mid = (low + high) / 2;
int dist = mid;
int ancestor1 = find_ancestor(X, dist);
int ancestor2 = find_ancestor(X, dist + 1);
// cout << low << ' ' << high << '\n';
// Check if we have the right answer
if (ancestor1 != -1 && ancestor2 != -1 && h[ancestor1] < h[C] && h[C] <= h[ancestor2]) {
ans = dist;
break;
}
// Anything that is greater or equal to C is not wanted.
if (ancestor1 == -1 || h[C] <= h[ancestor1]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
if (ans == -1) {
// There is nothing more to explore.
break;
}
else {
sum += ans;
int next = next_jump(find_ancestor(X, ans), C);
if (next == -1) {
break;
}
else if (next == C) {
found = true;
sum++;
break;
}
else {
sum++;
X = next;
}
}
}
if (found) {
return sum;
}
else {
return -1;
}
}
