#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 2e5 + 5;
const int INF = 2e9;
int n, h[lim], L[lim][18], R[lim][18], best[lim][18];
bool is_sub1 = true;
void init(int __n, vector<int>__h){
n = __n + 2;
__h.insert(__h.begin(), INF);
__h.push_back(INF);
stack<int>st;
for(int i = 0; i < n; st.push(i++)){
if((h[i] = __h[i]) != i && h[i] != INF){
is_sub1 = false;
}
while(!st.empty() && h[st.top()] < h[i]){
st.pop();
}
L[i][0] = (st.empty() ? i : st.top());
}
while(!st.empty()){
st.pop();
}
for(int i = n - 1; i > -1; st.push(i--)){
while(!st.empty() && h[st.top()] < h[i]){
st.pop();
}
best[i][0] = (h[L[i][0]] > h[R[i][0] = (st.empty() ? i : st.top())] ? L[i][0] : R[i][0]);
}
for(int j = 1; j < 18; j++){
for(int i = 0; i < n; i++){
L[i][j] = L[L[i][j - 1]][j - 1];
R[i][j] = R[R[i][j - 1]][j - 1];
best[i][j] = best[best[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D){
A++;
B++;
C++;
D++;
if(is_sub1){
return C - B;
}
if(A == B && C == D){
int ans = 0;
for(int i = 17; i > -1; i--){
if(h[best[A][i]] <= h[C]){
A = best[A][i];
ans |= 1 << i;
}
}
for(int i = 17; i > -1; i--){
if(h[R[A][i]] <= h[C]){
A = R[A][i];
ans += 1 << i;
}
}
return A == C ? ans : -1;
}
if(C == D){
maximize(A, L[C][0] + 1);
if(A > B){
return -1;
}
for(int i = 17; i > -1; i--){
if(R[A][i] <= B){
A = R[A][i];
}
}
int ans = 0;
for(int i = 17; i > -1; i--){
if(h[best[A][i]] <= h[C]){
A = best[A][i];
ans |= 1 << i;
}
}
for(int i = 17; i > -1; i--){
if(h[R[A][i]] <= h[C]){
A = R[A][i];
ans += 1 << i;
}
}
return ans;
}
if(B == C - 1){
return R[B][0] <= D ? 1 : -1;
}
int p = B + 1, ans = 0;
for(int i = 17; i > -1; i--){
if(R[p][i] < C){
p = R[p][i];
}
}
if(h[B] > h[p]){
return R[B][0] <= D ? 1 : -1;
}
for(int i = 17; i > -1; i--){
if(L[B][i] >= A && h[L[B][i]] < h[p]){
B = L[B][i];
}
}
if(L[B][0] >= A){
if(R[L[B][0]][0] <= D){
return 1;
}
}
else{
for(int i = 17; i > -1; i--){
if(h[best[B][i]] <= h[p]){
ans |= 1 << i;
B = best[B][i];
}
}
if(B == p){
return R[p][0] <= D ? ans + 1 : -1;
}
if(L[B][0] != 0 && R[L[B][0]][0] <= D){
return ans + 2;
}
}
for(int i = 17; i > -1; i--){
if(R[B][i] < C){
B = R[B][i];
ans += 1 << i;
}
}
return R[B][0] >= C && R[B][0] <= D ? ans + 1 : -1;
}
