#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
ll n, l;
vec<int> a;
vec<int> jumpRight, jumpLeft;
vec<vec<int>> up;
void init(int N, std::vector<int> H) {
n = N;
a = H;
jumpRight.assign(n,-1);
jumpLeft.assign(n,-1);
up.assign(n,vec<int>(20,-1));
stack<int> st;
for(int i = 0; i < n; i++) {
while(!st.empty() and a[st.top()] < a[i]) {
jumpRight[st.top()] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n - 1; i >= 0; i--) {
while(!st.empty() and a[st.top()] < a[i]) {
jumpLeft[st.top()] = i;
st.pop();
}
st.push(i);
}
for(int i = 0; i < n; i++) {
// get optimal: move left or move right
int lj = jumpLeft[i], rj = jumpRight[i];
if(lj == -1 and rj == -1) continue;
else if(lj == -1) up[i][0] = rj;
else if(rj == -1) up[i][0] = lj;
else {
if(a[lj] > a[rj]) {
up[i][0] = lj;
} else {
up[i][0] = rj;
}
}
}
for(int i = 1; i < 20; i++) {
for(int v = 0; v < n; v++) {
if(up[v][i-1] == -1) continue;
up[v][i] = up[up[v][i-1]][i-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
assert(A == B && C == D);
int at = A;
int hLim = a[C];
int ans = 0;
for(int i = 19; i >= 0; i--) {
if(up[at][i] == -1) continue;
if(a[up[at][i]] < hLim) {
ans += (1<<i);
at = up[at][i];
}
}
if(up[at][0] == C) return ans+1;
else return -1;
}
