#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;
int n, l;
vector<int> h;
vector<pair<int, int>> a;
vector<vector<int>> up, A;
void init(int N, std::vector<int> H)
{
n = N+1;
h = H;
l = ceil(log2(n));
h.push_back(n);
a.resize(n);
up.resize(n, vector<int>(l+1));
A.resize(n, vector<int>(l+1));
stack<int> st;
for(int i = 0; i < n; ++i){
while(!st.empty() && h[st.top()] < h[i]){
a[st.top()].second = i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
a[st.top()].second = st.top();
st.pop();
}
for(int i = n-1; i >= 0; --i){
while(!st.empty() && h[st.top()] < h[i]){
a[st.top()].first = i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
a[st.top()].first = st.top();
st.pop();
}
vector<int> inv_h(n+1);
for(int i = 0; i < n; ++i) inv_h[h[i]] = i;
for(int i = n; i > 0; --i){
int id = inv_h[i];
if(h[a[id].first] > h[a[id].second]) up[id][0] = a[id].first;
else up[id][0] = a[id].second;
A[id][0] = a[id].second;
// cerr << id << ' ' << up[id][0] << ' ';
for(int j = 1; j <= l; ++j){
up[id][j] = up[up[id][j-1]][j-1];
A[id][j] = A[A[id][j-1]][j-1];
// cerr << up[id][j] << ' ';
}
// cerr << endl;
// cout << a[id].first << ' ' << id << ' ' << a[id].second << endl;
}
}
int ans(int L, int R){
int ans = 0;
for(int i = l; i >= 0; --i){
if(h[up[L][i]] <= h[R]){
L = up[L][i];
ans += (1<<i);
}
}
for(int i = l; i >= 0; --i){
if(h[A[L][i]] <= h[R]){
L = A[L][i];
ans += (1<<i);
}
}
if(L == R) return ans;
return inf;
}
int minimum_jumps(int A, int B, int C, int D)
{
// return 0;
int res = inf;
for(int id = C; id <= D; ++id){
int mx = 0, mx_id = B;
for(int i = B; i >= A; --i){
if(h[i] > h[id]) break;
if(h[i] > mx){
mx = h[i];
mx_id = i;
}
}
res = min(res, ans(mx_id, id));
}
return (res == inf ? -1 : res);
}
