#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int heights[200002], N;
int L[200002][20], R[200002][20], high[200002][20];
void init(int N, vector<int> H) {
::N = N;
heights[0] = heights[N+1] = 6969420;
for (int i = 0; i < N; i++){
heights[i+1] = H[i];
}
stack<int> idx; idx.push(0);
for (int i = 1; i <= N; i++){
while (heights[idx.top()] < heights[i]) idx.pop();
L[i][0] = idx.top();
idx.push(i);
}
stack<int> idx2; idx2.push(N+1);
for (int i = N; i >= 1; i--){
while (heights[idx2.top()] < heights[i]) idx2.pop();
R[i][0] = idx2.top();
idx2.push(i);
high[i][0] = ((heights[L[i][0]] > heights[R[i][0]]) ? L[i][0] : R[i][0]);
}
R[N+1][0] = N+1;
for (int p = 1; p <= 19; p++){
R[N+1][p] = N+1;
for (int i = 1; i <= N; i++){
L[i][p] = L[L[i][p-1]][p-1];
R[i][p] = R[R[i][p-1]][p-1];
high[i][p] = high[high[i][p-1]][p-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
int furthest = B;
for (int i = 19; i >= 0; i--){
if (R[furthest][i] < C) furthest = R[furthest][i];
}
if (furthest == B){
if (R[B][0] <= D) return 1;
//else return -1;
}
int st = B;
for (int i = 19; i >= 0; i--){
if (L[st][i] >= A && heights[L[st][i]] < heights[furthest]) st = L[st][i];
}
if (L[st][0] >= A && R[L[st][0]][0] <= D) return 1;
int cur = st;
int ans = 0;
for (int i = 19; i >= 0; i--){
if (heights[high[cur][i]] <= heights[furthest]) {
cur = high[cur][i];
ans += 1 << i;
}
}
if (R[cur][0] >= C && R[cur][0] <= D) return ans+1;
if (L[cur][0] != 0 && R[L[cur][0]][0] <= D) return ans+2;
for (int i = 19; i >= 0; i--){
if (R[cur][i] < C){
cur = R[cur][i];
ans += 1 << i;
}
}
if (R[cur][0] <= D) return ans+1;
else return -1;
}
