#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e5;
const int INF = 1e9;
int kiri[MAXN + 5][20], kanan[MAXN + 5][20], best[MAXN + 5][20];
int H[MAXN + 5];
void init(int N, vector<int> h) {
H[0] = INF;
for(int i = 1; i <= N; i++) H[i] = h[i - 1];
H[N + 1] = INF;
for(int i = 1; i <= N; i++){
kiri[i][0] = i - 1;
while(H[kiri[i][0]] < H[i]) kiri[i][0] = kiri[kiri[i][0]][0];
for(int j = 1; j < 20; j++) kiri[i][j] = kiri[kiri[i][j - 1]][j - 1];
}
for(int j = 0; j < 20; j++) kanan[N + 1][j] = N + 1;
for(int i = N; i >= 1; i--){
kanan[i][0] = i + 1;
while(H[kanan[i][0]] < H[i]) kanan[i][0] = kanan[kanan[i][0]][0];
for(int j = 1; j < 20; j++) kanan[i][j] = kanan[kanan[i][j - 1]][j - 1];
}
for(int i = 1; i <= N; i++){
if(H[kiri[i][0]] > H[kanan[i][0]]) best[i][0] = kiri[i][0];
else best[i][0] = kanan[i][0];
}
for(int j = 1; j < 20; j++){
for(int i = 1; i <= N; i++) 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++;
int now = B;
for(int j = 19; j >= 0; --j){
if(kanan[now][j] < C){
now = kanan[now][j];
}
}
C = kanan[now][0];
if(C > D){
return -1;
}
now = C;
for(int j = 19; j >= 0; --j){
if(kanan[now][j] <= D){
now = kanan[now][j];
}
}
D = now;
now = B;
for(int j = 19; j >= 0; --j){
if(H[kiri[now][j]] < H[D] && kiri[now][j] >= A){
now = kiri[now][j];
}
}
int ans = 0;
for(int j = 19; j >= 0; --j){
if(H[best[now][j]] < H[C]){
ans += (1LL << j);
now = best[now][j];
}
}
if(kanan[now][0] >= C) return ans + 1;
else if(kiri[now][0] && kanan[kiri[now][0]][0] <= D) return ans + 2;
for(int j = 19; j >= 0; --j){
if(kanan[now][j] < C){
ans += (1LL << j);
now = kanan[now][j];
}
}
return ans + 1;
}
