#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;
using node = int;
struct segment_tree{
vector<node> t;
vector<int> a;
int n;
node merge(node l, node r){
return a[l] > a[r] ? l : r;
}
void build(int v, int l, int r){
if(l == r){
t[v] = l-1;
return;
}
int m = (l + r) >> 1;
build(v<<1, l, m);
build(v<<1|1, m+1, r);
t[v] = merge(t[v<<1], t[v<<1|1]);
}
node getmax(int v, int l, int r, int L, int R, int x){
if(a[t[v]] < x) return -1;
if(l == r) return t[v];
int m = (l + r) / 2;
if(R <= m) return getmax(v*2, l, m, L, R, x);
else if(L > m) return getmax(v*2+1, m+1, r, L, R, x);
else{
int ans = getmax(v*2+1, m+1, r, m+1, R, x);
if(ans != -1) return ans;
else return getmax(v*2, l, m, L, m, x);
}
}
node getmax(int L, int R, int x){
return getmax(1, 1, n, L+1, R+1, x);
}
node get(int v, int l, int r, int L, int R){
if(L == l && R == r)
return t[v];
int m = (l + r) >> 1;
if(R <= m) return get(v<<1, l, m, L, R);
else if(L > m) return get(v<<1|1, m+1, r, L, R);
else {
return merge(
get(v<<1, l, m, L, m),
get(v<<1|1, m+1, r, m+1, R)
);
}
}
node get(int L, int R){
return get(1,1,n,L+1, R+1);
}
segment_tree(vector<int>a):a(a){
n = (int)a.size();
t.resize(n<<2);
build(1, 1, n);
}
segment_tree() {}
};
segment_tree st;
int ok = 1;
void init(int N, std::vector<int> H)
{
for(int i = 0; i < N; ++i) ok &= (H[i] == i+1);
cin.tie(nullptr)->sync_with_stdio(false);
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));
st = segment_tree(h);
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)
{
if(ok) return C - B;
// return 0;
int res = inf;
for(int id = C; id <= D; ++id){
if(h[B] > h[id]) continue;
int L = st.getmax(A, B, h[id]);
// cerr << "\n----" << L << "---\n";
int mx_id = st.get(max(L+1, A), B);
// 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);
}
